Submission #1360011

#TimeUsernameProblemLanguageResultExecution timeMemory
1360011FZ_LaabidiBikeparking (EGOI24_bikeparking)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

int f(int k, vector<int> x, vector<int> y){
    int ix=0, iy=0, n = x.size();
     int pos = 0, neg = k;
    while (k>0){
        if(y[iy]==0){
            iy++; 
            continue;
        }
        int c = min(k, y[iy]);
        k-=c;
        y[iy]-=c;
    }
   
    while(iy<n){
        if(y[iy]==0){
            iy++;
            continue;
        }
        if(x[ix]==0){
            ix++;
            continue;
        }
        int c = min(y[iy], x[ix]);
        x[ix]-=c;
        y[iy]-=c;
        if(ix<iy)pos+=c;
         if(ix>iy)neg+=c;
    }
    return pos-neg;
}
int df(int k, vector<int> x, vector<int> y){
    return f(k+1, x, y)-f(k, x, y);
}
signed main(){
    int n; cin >> n;
    vector<int> x(n), y(n);
    for(int i=0; i<n; i++)cin >> x[i];
    for(int i=0; i<n; i++)cin >> y[i];
    if(n==1)cout << 0 << endl;
    else{
        int k=0;
        for(auto it: y)k+=it;
        int l=0, r= k-1;
        while (l<r){
            int m = (l+r+1)/2;
            int vo = df(m, x, y);
            if(vo<0)r = m-1;
            else if(vo==0) l = m, r = m;
            else  l = m;

        }
        cout <<  f(l+1, x, y);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...