Submission #813475

#	Time	Username	Problem	Language	Result	Execution time	Memory
813475		peteza	Art Exhibition (JOI18_art)	C++14	100 / 100	142 ms	24788 KiB

art

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
ll a, b;
vector<pair<ll, ll>> vec;
ll ans = 0;
ll qs[500005];

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    vec.resize(n);
    for(auto &e:vec) {
        cin >> a >> b;
        e = pair<ll, ll>(a, b);
        ans = max(ans, b);
    }
    sort(vec.begin(), vec.end());
    qs[0] = vec[0].second;
    for(int i=1;i<n;i++) qs[i] = qs[i-1] + vec[i].second;
    qs[n-1] = qs[n-1] - vec[n-1].first;
    for(int i=n-2;i>=0;i--) qs[i] = max(qs[i+1], qs[i] - vec[i].first);
    ll cur = 0;
    for(int i=0;i<n;i++) {
        ans = max(ans, qs[i]-cur+vec[i].first);
        cur += vec[i].second;
    }
    cout << ans;
}

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