please see into my code the other submission with the same use of prefix sum algorithm is getting acccecpted while mine is showing TLE and WA on some of the cases.
please help me out
Your solution gives TLE because it’s complexity is O(n^2). We have to use two pointers in this problem or we can use prefix sums with binary search. My solution which uses prefix sum and binary search : Submission #14766605 - AtCoder Beginner Contest 172
Thank You
bro check out this submission this is too O(n^2) but all the cases are AC how?
Okay, so ur code gives WA in some subtasks because u are just keeping ans = i+j, whereas it should be ans = max(ans, i+j). Doing this will remove ur WA.
Now ur code gives TLE because in ur code for every i u search for b[j] from m. Whereas in the others man code whenever he finds a[i] + b[j] <= k,he changes the value of his bestj to j.
Correct code of urs with some slight modifications :
I hope u understood
yes thank you very much
Do not use ( this for love u ) , use this warna bahut pange ho jaaynge
U can understand with my solution too -
int main(){
fastio
lli t=1;
while(t--) {
lli n,m,k;
cin>>n>>m>>k;
lli a[n] , b[m];
scanarr(a,n);
scanarr(b,m);
FOR(i,1,n)
{
a[i]+=a[i-1];
}
FOR(i,1,m)
{
b[i]+=b[i-1];
}
lli ans = upper_bound(b,b+m,k)-b;
lli maxi = ans;
loop(i,n){
if(a[i]<=k){
lli count = upper_bound(b,b+m,k-a[i])-b;
maxi = max(maxi , (i+1+count));
}
else
break;
}
print(maxi);
}
return 0;
}
bhai mai nya hun maaf kar dio