Submission #1250592

#TimeUsernameProblemLanguageResultExecution timeMemory
1250592LaMatematica14Art Exhibition (JOI18_art)C++20
100 / 100
435 ms43704 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int N; cin >> N;
    map<long long, long long> A;
    for (int i = 0; i < N; i++) {
        long long a, b; cin >> a >> b;
        if (A.count(a)) A[a] += b;
        else A.insert({a, b});
    }
    
    N = A.size();
    vector<long long> aus, h;
    for (auto i : A) {
        aus.push_back(i.second);
        h.push_back(i.first);
    }
    aus.push_back(0);
    for (int i = N-1; i >= 0; i--) aus[i] += aus[i+1];
    vector<long long> mass(N);
    mass[0] = aus[0]+h[0];
    for (int i = 1; i < N; i++) {
        mass[i] = max(mass[i-1], aus[i]+h[i]);
    } 
    long long best = -1000000000000000;
    for (int i = 0; i < N; i++) {
        best = max(best, mass[i]-h[i]-aus[i+1]);
    }
    cout << best << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...