제출 #800326

#제출 시각아이디문제언어결과실행 시간메모리
800326leeminhduc2Potatoes and fertilizers (LMIO19_bulves)C++17
30 / 100
1075 ms11064 KiB
///leeminhduc2 #include <bits/stdc++.h> #define ll long long #define f first #define s second #define ii pair<int,int> #define sz(x) (int) (x).size() #define pb push_back using namespace std; template<class T1,class T2> bool maximize(T1 &a,T2 b) {return(a<b ? a=b,1:0);}; template<class T1,class T2> bool minimize(T1 &a,T2 b) {return(a>b ? a=b,1:0);}; int n; ll a,b,lst,d[500010]; void leeminhduc2() { cin >> n; a=0,b=0; priority_queue<ll> pq; for( int i=1;i<=n;i++) { ll u,v; cin >> u >> v; d[i]=u-v; d[i]+=d[i-1]; //cout <<d[i] << " "; } for (int i=1;i<=n;i++) { ll x; x=d[i]; if (x>=0){ ++a; pq.push(x); pq.push(x); b-=x; } else { ++a; pq.push(0ll); b-=x; } if (i<n){ while (sz(pq)&&a>=0) { ll cur=pq.top(),cnt=0; while (sz(pq)&&cur==pq.top()) { ++cnt; pq.pop(); } a-=cnt; b+=cur*cnt; lst=cur; } for (int j=1;j<=-a;j++) pq.push(lst); b+=lst*a; a=0; } else { while (sz(pq)&&pq.top()>=d[n]) { ll cur=pq.top(),cnt=0; while (sz(pq)&&cur==pq.top()) { ++cnt; pq.pop(); } a-=cnt; b+=cur*cnt; lst=cur; } } } cout << a*d[n]+b; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); leeminhduc2(); }
#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...