Submission #1117195

#TimeUsernameProblemLanguageResultExecution timeMemory
1117195vjudge1Art Exhibition (JOI18_art)C++14
100 / 100
143 ms28752 KiB
#include <bits/stdc++.h>
#define sts(v) stable_sort(v.BE, v.E)
#define Rsts(v) stable_sort(v.rBE, v.rE)
#define rev(v) reverse(v.BE, v.E)
#define BE begin()
#define rBE rbegin()
#define E end()
#define rE rend()
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define F first
#define S second

using namespace std;
using ll = long long;

int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    int n; cin >> n;
    vector<pair<ll, ll>> v(n + 1);

    for(int i = 1; i <= n; i++){
        ll a, b; cin >> a >> b;

        v[i] = {a, b};
        //a -> size b -> val
    }

    sts(v);
    
    int pos = 0;
    ll res = 0, ans[n + 1];
    ans[0] = 0;
    for(int i = 1; i <= n; i++){
        ll a = v[i].S, b = ans[pos] - v[i].F + v[i].S;

        ans[i] = max(a, b);
        res = max(res, ans[i]);
        ans[i] += v[i].F;
        if(ans[i] > ans[pos])pos = i;       
    }   

    cout << res << '\n';
	
    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...