Submission #1196948

#TimeUsernameProblemLanguageResultExecution timeMemory
1196948amanthabandArt Exhibition (JOI18_art)C++20
50 / 100
1093 ms19764 KiB
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

using ll = long long;
ll mod = 100000000000007;

ll modpow(ll a, ll b) {
    ll result = 1;
    a %= mod;
    while (b > 0) {
        if (b % 2 == 1)
            result = (result * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return result;
}

ll solve(ll n, vector<pair<ll, ll>> arr) {
    vector<ll> pre(n + 1);
    for (ll i = 0; i < n; ++i) {
        pre[i + 1] = pre[i] + arr[i].second;
    }
    ll ans = 0;
    for (ll i = 0; i < n; ++i) {
        ll mx = arr[i].first;
        ll mn = arr[i].first;
        for (ll j = i; j < n; ++j) {
            mx = max(mx, arr[j].first);
            mn = min(mn, arr[j].first);
            ll h = pre[j + 1] - pre[i];
            ans = max(ans, h - (mx - mn));
        }
    }
    return ans;
}

int main() {
    ll n;
    cin >> n;

    vector<pair<ll, ll>> vec(n);

    for (int i = 0; i < n; i++) {
        ll k, m;
        cin >> k >> m;
        vec[i] = {k, m};
    }

    sort(vec.begin(), vec.end());
    ll ans = solve(n, vec);
    cout << ans << endl;

    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...