Submission #1331304

#TimeUsernameProblemLanguageResultExecution timeMemory
1331304lywoemArt Exhibition (JOI18_art)C++20
100 / 100
133 ms19936 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define l(a, b, i) for (ll i = a; i < b; i++)
#define rl(a, b, i) for (ll i = a; i >= b; i--)
#define vpair vector<pair<ll, ll>>
#define inf LLONG_MAX
#define ninf LLONG_MIN

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll N; cin >> N; vector<ll> sz(N + 1, 0), val(N + 1, 0); vector<pair<ll, ll>> vec(N + 1);
    l(1, N + 1, i) {
        cin >> sz[i] >> val[i];
        vec[i] = {sz[i], val[i]};
    }
    sort(vec.begin() + 1, vec.end()); // sort theo increasing size nhé

    vector<ll> pre(N + 1, 0); // prefix cái val á   
    l(1, N + 1, i) pre[i] = pre[i - 1] + vec[i].second;

    ll ans = ninf;
    ll curmin = vec[1].first;

    l(1, N + 1, i) {
        ans = max(ans, pre[i] - vec[i].first + curmin);
        if (i + 1 <= N) curmin = max(curmin, vec[i + 1].first - pre[i]); 
    }

    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...