제출 #1359974

#제출 시각아이디문제언어결과실행 시간메모리
1359974ma_moutahidBikeparking (EGOI24_bikeparking)C++20
100 / 100
207 ms14620 KiB
#include <bits/stdc++.h>
#define vi vector<int>
using ll=long long;
#define int ll


using namespace std;

int f(int k, vector<int>x, vector<int>y){

    int n=x.size();
    int u=0;
    int d=k;
    int ix=0;//index in x
    int iy=0;//index in y

    //remove k people
    while(k){
        if(y[iy]==0){
            iy++;
            continue;
        }
        int c=min(k,y[iy]);
        k-=c;
        y[iy]-=c;
    }

    //assign everyone in y to the lowest possible x
    while(iy<n){
        if(y[iy]==0){
            iy++;
            continue;
        }
        if(x[ix]==0){
            ix++;
            continue;
        }
        int c=min(x[ix],y[iy]);
        x[ix]-=c;
        y[iy]-=c;
        if(ix>iy)d+=c;
        if(ix<iy)u+=c;
    }
    return u-d;
}

inline int slope(int k, vector<int>&x,vector<int>&y){
    return f(k+1,x,y)-f(k,x,y);
}


signed main() {
    int n;
    cin>>n;
    vi x(n);
    vi y(n);
    for(int &i:x)cin>>i;
    for(int &i:y)cin>>i;

    int sum= accumulate(y.begin(),y.end(),0ll);
    int l=0,r=sum;
    while(r>l){
        int m=(l+r)/2;
        if(slope(m,x,y)<0)r=m;
        else l=m+1;
    }
    int result=f(l,x,y);

    cout<<result<<endl;


    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…