Submission #1250592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250592		LaMatematica14	Art Exhibition (JOI18_art)	C++20	100 / 100	435 ms	43704 KiB

art

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

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