Submission #753980

#	Time	Username	Problem	Language	Result	Execution time	Memory
753980		hung0109ie	Art Exhibition (JOI18_art)	C++14	100 / 100	763 ms	15992 KiB

art

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int maxn = 5e5+1;
int n;
pair<ll, ll> a[maxn];
ll prefix[maxn];
ll mn, ans;

int main(){
    mn = 1e17;
    ans = 0;
    prefix[0]=0;
    cin>>n;
    for(int i = 1; i<=n; i++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1, a+n+1);
    for(int i = 1; i<=n; i++){
        prefix[i] = prefix[i-1] + a[i].second;
    }
    for(int j = 1; j<=n; j++){
        if(prefix[j-1]-a[j].first<mn) mn = prefix[j-1]-a[j].first;
        if(ans < prefix[j]-a[j].first-mn) ans = prefix[j]-a[j].first-mn;
    }
    cout<<ans;
}

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