Submission #1084362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084362		s_mtOJ	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	150 ms	11220 KiB

bulves

#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// #define F first
// #define S second
// #define pb push_back
// #define EB emplace_back
// #define MP make_pair
#define all(o) (o).begin(), (o).end()
#define rall(o) (o).rbegin(), (o).rend()
// #define mset(m,v) memset(m,v,sizeof(m))
// #define fr(i,n) for(ll i=0;i<n;++i)
// #define rep(i,a,b) for(ll i=a;i<=b;++i)
// #define per(i,a,b) for(ll i=a;i>=b;i--)
// #define amin(a,b) (a=min((a),(b)))
// #define amax(a,b) (a=max((a),(b))) 
#define sz(x) (ll)(x).size()
typedef long long ll;         typedef long double ld;
// typedef pair<ll,ll> ii;       typedef vector<ll> vi;
// typedef vector<ii> vii;       typedef vector<vi> graph;
// long long md=1e9+7;           long double EPS=1e-9;
// const double Pi=3.1415926535897932384626433832795;
// const int N=100100;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #define debarr(a,n) cout<<#a<<" : ";for(int i=0;i<n;i++) cerr<<a[i]<<" "; cerr<<endl;
// #define Haan cout<<"YES\n";
// #define Naah cout<<"NO\n";
// #define debmat(mat,row,col) cout<<#mat<<" :\n";for(int i=0;i<row;i++) {for(int j=0;j<col;j++) cerr<<mat[i][j]<<" ";cerr<<endl;}
// #define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
// template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
// template <class T>istream& operator>>(istream &is, vector<T> &a){for (auto &it : a)is >>it;return is;}
// template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os<< "[ "; for (auto& it : p) os << it << " "; return os << "]";}
// template <class S, class T>ostream& operator <<(ostream& os, const unordered_map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
// template <class T>ostream& operator <<(ostream& os, const unordered_set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
// template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
// template <class T>ostream& operator <<(ostream& os, const multiset<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
// template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
// template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
// template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
// template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}
// ll binpowMD(ll b,ll p,ll mod){ll ans=1;b%=mod;for(;p;p>>=1){if(p&1)ans=ans*b%mod;b=b*b%mod;}return ans;}
// ll binpow(ll b,ll p){ll ans=1;for(;p;p>>=1){if(p&1)ans=ans*b;b=b*b;}return ans;}
// ll fact[2*N],ifact[2*N];
// void factorials(){
// fact[0]=fact[1]=1;
// for(int i=1;++i<2*N;)fact[i]=fact[i-1]*i%md;
// ifact[2*N-1]=binpowMD(fact[2*N-1],md-2,md);
// for(int i=2*N;--i>0;)ifact[i-1]=ifact[i]*i%md;
// }

// ll nCr(ll n,ll r){
// if(n<r) return 0;
// return  ((fact[n])*(ifact[n-r]*ifact[r]%md))%md;
// }

// void precompute(){
// return;
// factorials();
// }
void testCases(){
    int n;
    cin>>n;
    // vector<int> v(n+1,0);

    ll p=0;
    priority_queue<ll> pq;
    ll ans=0;

    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
         p=a-b+p;
         ll tp=p;
         if(tp<0)ans-=p,tp=0;
         ans+=tp;
         pq.push(tp);
         pq.push(tp);
         pq.pop();
    }

    while (pq.empty()==false)
    {
        ans-=min(pq.top(),p);
        pq.pop();
    }
    

    cout<<ans<<"\n";

    
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// #ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// freopen("output.txt", "w", stderr);
// #endif
// precompute();
ll _t=1;
// cin>>_t;
for(ll i=1;i<=_t;i++){
        //cout<<"Case #"<<i<<": ";
            testCases();
}
}
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⣾⣿⣿⣿⣿⣷⣦⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀  ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀   ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀   ⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⣄⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⢼⣿⣿⣿⣿⣿⣿⣿⣿   ⣸⡄⠀  ⠤⠤⠤⠤⠤⠤⠤⠄   ⠀⣷⡀  ⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠀⠀
// ⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿   ⡇⢧⠀⠀⠤⠤⠤⠤⠤⠤⠤⠄   ⢰⠋⡇  ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿   ⡇⠈⢦⠀⠤⠤⠤⠤⠤⠤⠤⠄ ⣠⠃⢰⠇  ⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿   ⠘⣄⠀⠙⠤⣄⡀⠀⠀⠀⣀⡤⠚⠁⢠⠎    ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠀⠀⠀
// ⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿    ⠈⠑⠢⠤⠔⠋⠁⠀⠙⠒⠤⠴⠚⠁     ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⠀⠀⠀
//      ⣿⣿⣿⣿⣿⣿⣿⣿⣵⣿⣿⣟⣛⣛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣻⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀
//      ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣏⣯⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿ ⠀⠀
//      ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢸⣿⣿⣿⣿⣿⣿⣿⠀⠀
// ⠀   ⣿⣿⣿⣿⣿⣿⣿⣿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿  ⣿⣿⣿⣿⣿⣿⣿ 
// ⠀  ⠀⣿⣿⣿⣿⣿⣿⣿⡏⠀⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣻⣿⢿⣿⣿⣿⣿⣿⣿  ⣿⣿⣿⣿⣿⣿⡿⠀
// ⠀    ⣿⣿⣿⣿⣿⣿⣷  ⣿⣿⣿⣿⣿⣿⡿⣿⣿⢿⡿⡿⢿⣯⢻⡼⣷⢰⣿⣿⣿⣿⣿⣿⡇⠀⣿⣿⣿⣿⣿⣿⡗⠀
//       ⢹⣿⣿⣿⣿⣿   ⣿⣿⣯⣼⡛⣧⠻⢿⢸⡇⣿⣿⣿⣼⣧⣿⣮⣿⣿⣿⣿⣿⣿⣇⠀ ⣿⣿⣿⣿⣿⡧⠀
// ⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿   ⣿⣿⣿      ⠺⠂⠀⠀⠀⣷⠀⠀           ⣿⣿ ⢸⣿⣿⣿⣿⣿⠁
// ⣿⣶⣦⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿  ⣿⠞⠃⣿⡇⣼⠏⠻⣿⢠⣞⣉⣿ ⣿⠟⠙⠃ ⣿⣿ ⣸⣿⣿⣿⣿⡟⠀⠀⠀⠀⠀⠀⠀
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿  ⣿⠀⠀⣿⡇⢻⣦⣴⣿⠘⣯⣉⣩⠀⣿⠀⠀  ⢸⣿⣿ ⣿⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⢉⣿⣿⠤⠤⠤⠤⠤⠤⠤                      ⣿⣷⣿⣿⣿⣿⣿⠛⠀⠀⠀⠘⣼
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⠸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⣠⣼⣿
// ⣿⡛⢛⣿⣿⣿⣿⣿⣿⣶⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣿⣿⣿⣿⡿⠀⠀⠀⣸⣿⠏
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⢀⣀⣼⣿⠟⠀
/*********************$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$************************/

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