Submission #750636

#	Time	Username	Problem	Language	Result	Execution time	Memory
750636		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	213 ms	20992 KiB

art

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define pii pair<ll,ll>
#define f first
#define s second

const int N = 5e5+5;
int n;
pii art[N];

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> art[i].f >> art[i].s;
    }

    sort(art, art+n);

    ll ans = art[0].s, curr = art[0].s, sum = art[0].s, prev = 0;
    for(int i = 1; i < n; i++){
        if(sum < art[i].f-art[prev].f){
            prev = i;
            curr = sum = art[i].s;
        } else {
            sum += art[i].s;
            curr = sum-(art[i].f-art[prev].f);
        }
        ans = max(ans, curr);
    }

    cout << ans << "\n";


    return 0;
}

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