Submission #1343102

#TimeUsernameProblemLanguageResultExecution timeMemory
1343102curious_tigerArt Exhibition (JOI18_art)C++20
100 / 100
374 ms43684 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n; cin >> n;
    map<ll, ll> size_to_value;
    ll a, b;
    for (ll i=0; i<n; i++) {
        cin >> a >> b;
        size_to_value[a] += b;
    }
    vector<ll> A, B;
    for (const auto &[key, value] : size_to_value) {
        A.push_back(key);
        B.push_back(value);
    }
    n = size_to_value.size();
    vector<ll> ps_B (n+1, 0);
    for (ll i=0; i<n; i++) {
        ps_B[i+1] = ps_B[i] + B[i];
    }

    // // O(n^2) algorithm
    // ll ans = LLONG_MIN, x = LLONG_MAX;
    // for (ll i=0; i<n; i++) {
    //     for (ll j=i; j<n; j++) {
    //         ll score = ps_B[j+1] - A[j] - (ps_B[i] - A[i]);
    //         ans = max(ans, score);
    //     }
    // }

    // O(n) algorithm
    ll ans = LLONG_MIN, x = LLONG_MAX;
    for (ll i=0; i<n; i++) {
        x = min(x, ps_B[i] - A[i]);
        ans = max(ans, ps_B[i+1] - A[i] - x);
    }

    cout << ans << "\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...