Submission #1347566

#TimeUsernameProblemLanguageResultExecution timeMemory
1347566ChottuFArt Exhibition (JOI18_art)C++20
100 / 100
314 ms15912 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    int n;
    cin >> n;
    pair<int,int> arr[n];
    for (int i = 0; i<n; i++){
        int a,b;
        cin >> a >> b;
        arr[i] = {a,b};
    }
    sort(arr,arr+n);
    vector<int> pf(n+1, 0);
    vector<int> sf(n, 0);
    
    for (int i = 1; i<=n; i++){
        pf[i] = pf[i-1] + arr[i-1].second;
    }
    for (int i = 0; i<n; i++){
        sf[i] = pf[i+1] - arr[i].first;
    }
    for (int i = n-2; i>=0; i--){
        sf[i] = max(sf[i], sf[i+1]);
    }
    int ans = 0;
    for (int i = 0; i<n; i++){
        int one = arr[i].first - pf[i];
        int two = sf[i];
        ans = max(ans, one+two);
    }
    cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...