Submission #1033967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033967		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	508 ms	40084 KiB

art

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define bip(i) __builtin_popcount(i)
#define gb(i,j) ((i>>j)&1)

using namespace std;

const int N=5e5+5;
int n , vt;
map<ll , ll>dem;
ll s[N] , f[N] , a[N] , Min=1e18 , res;

int main()
{
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n;
    for( int i=1 ; i<=n ; i++ ){
        ll u , v;
        cin >> u >> v;
        if(dem[u]==0) a[++vt]=u;
        dem[u]+=v;
    }
    sort(a+1 , a+1+vt);
    Min = min( Min , s[0]-a[1] );
    for( int i=1 ; i<=vt ; i++ ){
//        cout << i << " " << s[]
        s[i] = s[i-1]+dem[a[i]];
        res = max( res , s[i]-a[i] - Min );
        Min = min( Min , s[i]-a[i+1] );
    }
    cout << res;
}

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