Submission #1208098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208098		ffeyyaae_	Art Exhibition (JOI18_art)	C++20	50 / 100	160 ms	15956 KiB

art

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

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