Submission #1319327

#TimeUsernameProblemLanguageResultExecution timeMemory
1319327yessimkhanArt Exhibition (JOI18_art)C++20
100 / 100
264 ms35632 KiB
#include <bits/stdc++.h>
// solved by bekagg
#define int long long
#define ent '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

const int N = 5e5+5;
const int MOD = 1e9+7;

int n , pref[N];
vector<pair<int , int> > v;

void arkanefury228(){

    cin >> n;

    int ans = 0;

    for (int i = 1; i <= n; i++){
        int a , b;
        cin >> a >> b;
        ans = max(ans , b);
        v.pb({a , b});
    }

    sort(all(v));

    multiset<int>s;

    for (int i = 1; i <= n; i++){
        pref[i] = pref[i - 1] + v[i - 1].second;
        s.insert(pref[i] - (v[i - 1].first - v[0].first));
    }

    int sum = 0;

    ans = max(ans , *s.rbegin());

    for (int i = 1; i < n; i++){
        s.erase(s.find(pref[i] - (v[i - 1].first - v[0].first)));
        sum += (v[i].first - v[i - 1].first);
        sum -= v[i - 1].second;
        ans = max(ans , *s.rbegin() + sum);
    }

    cout << ans;
}

signed main(){

    PRaim_bek_abi

    int t=1;
    //cin>>t;
    for (int respagold = 1; respagold <= t; respagold++) arkanefury228();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...