제출 #1208098

#제출 시각아이디문제언어결과실행 시간메모리
1208098ffeyyaae_Art Exhibition (JOI18_art)C++20
50 / 100
160 ms15956 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 5e+5;
const ll INF = LLONG_MAX/2;

int n;
vector<pair<ll,int>> vec;
ll a[N], qs[N];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    vec.resize(n);
    for( auto &[a, b] : vec ) cin >> a >> b;
    sort( vec.begin(), vec.end() );
    for( int i=1;i<=n;i++ )
    {
        a[i] = vec[i-1].first;
        qs[i] = qs[i-1]+vec[i-1].second;
        //cout << a[i] << " " << qs[i] << endl;
    }
    ll ans = 0, mx = -INF;
    for( int i=1;i<=n;i++ )
    {
        mx = max( mx, a[i]-qs[i-1] );
        ans = max( ans, -a[i]+qs[i]+mx );
        //cout << "mx " << mx << " ans " << ans << endl;
    }
    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...