Submission #499306

#	Time	Username	Problem	Language	Result	Execution time	Memory
499306		Marceantasy	Art Exhibition (JOI18_art)	C++17	100 / 100	206 ms	20928 KiB

art

#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";
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50