Submission #349486

#	Time	Username	Problem	Language	Result	Execution time	Memory
349486		rivalq	Potatoes and fertilizers (LMIO19_bulves)	C++17	0 / 100	1 ms	492 KiB

bulves

// Jai Shree Ram  
  
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}


int solve(){
 	int n;cin>>n;
 	priority_queue<int>pq;
 	int x,y;
 	vector<int>a(n+1);
 	rep(i,1,n+1){
 		cin>>x>>y;
 		a[i]=x-y;
 		a[i]+=a[i-1];
 	}
 	int ans=0;
 	rep(i,1,n+1){
 		if(a[i]>a[n]){
 			ans+=a[i]-a[n];
 			a[i]=a[n];
 		}
 	} 	
 	if(a[1]<0)ans-=a[1],a[1]=0;
 	pq.push(a[1]);
 	rep(i,2,n){
 		int s=a[i];
 		auto itr=pq.top();
 		if(itr>s){
 			ans+=abs(itr-s);
 			pq.pop();
 			pq.push(s);
 			pq.push(s);
 		}
 		else{
 			pq.push(s);

 		}
 	}
 	cout<<ans<<endl;
 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
 

• Subtask 1: 0 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36