Submission #824203

#	Time	Username	Problem	Language	Result	Execution time	Memory
824203		SoulKnight	Art Exhibition (JOI18_art)	C++17	100 / 100	143 ms	24732 KiB

art

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

#define ll long long
#define ln '\n'

const int N = 5e5 + 5;
const int LG = 20;
const int INF = 2e9 + 5;
const int MOD = 998244353;

int n;
pair<ll, ll> a[N];
ll pfx[N];

void init(){
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
    }
}

ll solve(){
    sort(a, a+n);
    pfx[0] = a[0].second;
    for (int i = 1; i < n; i++) pfx[i] = pfx[i-1] + a[i].second;
    ll ans = 0LL, mx = 0LL;

    for (int i = 0; i < n; i++){
        mx = max(mx, a[i].first - ((i-1 < 0)? 0LL: pfx[i-1]));
        ans = max(ans, pfx[i] + mx - a[i].first);
    }

    return ans;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("mooyomooyo.in", "r", stdin);
    // freopen("mooyomooyo.out", "w", stdout);


    // ll T; cin >> T;
    // while (T--){
    //     solve();
    // }

    init();
    cout << solve();


    return 0;
}

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