Submission #794269

#TimeUsernameProblemLanguageResultExecution timeMemory
794269dimashhhArt Exhibition (JOI18_art)C++17
100 / 100
164 ms24660 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 123;

int n;
vector<pair<ll,ll>> a(N);
ll p[N];
//dp[i] = p[i] - p[j - 1] - (a[i] - a[j]) = p[i] - a[i] - (p[j - 1] - a[j])
//
void test(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin() + 1,a.begin() + n + 1);
    ll vl = -a[1].first;
    for(int i = 1;i <= n;i++){
        p[i] = p[i - 1] + a[i].second;
    }
    ll res ;
    for(int i = 1;i <= n;i++){
        vl = min(vl,p[i - 1] - a[i].first);
        if(i == 1) res = p[i] - a[i].first - vl;
        else res = max(res,p[i] - a[i].first - vl);
    }
    cout << res;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) test();
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...