제출 #716702

#제출 시각아이디문제언어결과실행 시간메모리
716702vjudge1Art Exhibition (JOI18_art)C++17
100 / 100
694 ms46096 KiB
#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;
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...