제출 #1339631

#제출 시각아이디문제언어결과실행 시간메모리
1339631athenaBikeparking (EGOI24_bikeparking)C++20
100 / 100
40 ms22140 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<int>arr(n),brr(n);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    for(int i=0;i<n;i++)
        cin>>brr[i];
    vector<int>x(arr.begin(),arr.end());
    vector<int>y(brr.begin(),brr.end());
    vector<tuple<int,int,int>>stk;
    int left=0;
    int ans=0;
    for(int i=0;i<n;i++)//try to put ppl in slots above their pay
    {
        while(!stk.empty()&&y[i]>0)
        {
            auto &[b,slot,prevleft]=stk.back();
            int c=left-prevleft;
            if(c>0)break;
           
             int assign=min(y[i],slot);
             ans+=assign;
             y[i]-=assign;
             x[b]-=assign;
             slot-=assign;
             if(slot==0)
             stk.pop_back();
        }
        left+=y[i];
         if(x[i]>0)
       {
        stk.push_back({i,x[i],left});
       }
       }
      
   // }
    for(int i=0;i<n;i++)
    {
        int a=min(x[i],y[i]);
            x[i]-=a;
            y[i]-=a;
        
    }
    for(int i=0;i<n;i++)
    {
            ans-=y[i];
    }
    cout<<ans<<endl;
    return 0;
}
#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...