제출 #1359995

#제출 시각아이디문제언어결과실행 시간메모리
1359995FZ_LaabidiBikeparking (EGOI24_bikeparking)C++20
16 / 100
1095 ms7476 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;
}
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;
        while (l<r){
            int m = (l+r)/2;
            //cout <<  l << " "<< m << " "<<r << " "<< f(m, x, y)<< endl;
            int vo = f(m+1, x, y)-f(m, x, y);
            if(vo<0)r = m-1;
            else if(vo==0) l = m, r = m;
            else  l = m;

        }
        cout <<  f(l, 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...