Submission #716702

#	Time	Username	Problem	Language	Result	Execution time	Memory
716702		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	694 ms	46096 KiB

art

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define oo 1e15 + 9
#define pii pair<ll, ll>

int main(){
    int n; cin >> n;
    pii arr[n];
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].first >> arr[i].second;
    }
    sort(arr, arr + n);
    ll PreSum[n + 1];
    PreSum[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        PreSum[i] = PreSum[i - 1] + arr[i - 1].second;
    }
    multiset<ll> s; 
    for (int i = 1; i <= n; i++)
    {
        s.insert(PreSum[i] - arr[i - 1].first);
    }
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        ll b = *prev(s.end());
        ans = max(ans, b - PreSum[i] + arr[i].first);
        s.erase(s.find(PreSum[i + 1] - arr[i].first));
    }
    cout << ans;
    
}

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