Https://atcoder.jp/contests/abc172/tasks/abc172_c

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 :slight_smile:

1 Like

bro check out this submission this is too O(n^2) but all the cases are AC how?

1 Like

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 :slightly_smiling_face:

1 Like

yes :love_you_gesture: thank you very much

Do not use :love_you_gesture: ( this for love u ) , use this :metal: warna bahut pange ho jaaynge :rofl:

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;
}

Solution

1 Like

bhai mai nya hun maaf kar dio

1 Like