Submission #499306

#TimeUsernameProblemLanguageResultExecution timeMemory
499306MarceantasyArt Exhibition (JOI18_art)C++17
100 / 100
206 ms20928 KiB
#include <bits/stdc++.h>
using namespace std; 

#define ll long long
#define ar array

const int mxN = 2e5+1, M = 1e9+7; 

int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
    
    int n; 
    cin >> n; 
    vector<pair<ll, ll>> a(n+1);
    for(int i = 1; i<=n; ++i){
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end());
    for(int i = 1; i<=n; ++i){
        a[i].second += a[i-1].second;
    }
    ll mx = -1e18, ans = 0; 
    for(int i = 1; i<=n; ++i){
        mx = max(mx, a[i].first - a[i-1].second);
        ans = max(ans, -a[i].first + a[i].second + mx);
    }
    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...