Submission #678505

#	Time	Username	Problem	Language	Result	Execution time	Memory
678505		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	172 ms	12524 KiB

art

#include<bits/stdc++.h>
using namespace std;
pair <long long,long long> a[500100];
long long best[500100];
long long n;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for (long long i = 1;i <= n;i ++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+1+n);
    for (long long i = 1;i <= n;i ++){
        a[i].second += a[i-1].second;
    }
    for (long long i = n;i >= 1;i --){
        best[i] = a[i].second - a[i].first;
        if (i < n)best[i] = max(best[i],best[i+1]);
    }
    long long ans = -1;
    for (long long i = 1;i <= n;i ++){
        ans = max(ans,best[i] - a[i-1].second + a[i].first);
    }
    cout<<ans<<'\n';
    return 0;
}

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