Submission #1196948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196948		amanthaband	Art Exhibition (JOI18_art)	C++20	50 / 100	1093 ms	19764 KiB

art

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

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