Submission #146448

#	Time	Username	Problem	Language	Result	Execution time	Memory
146448		MathStudent2002	Art Exhibition (JOI18_art)	C++14	100 / 100	268 ms	28660 KiB

art

//wait darn

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef long long ll;
typedef pair<ll,ll> art;

const int MAXN = 1024576;

int N;
art muse[MAXN];
ll cost[MAXN];
ll psum[MAXN];

void input() {
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> muse[i].x >> muse[i].y;
    }
    sort(muse, muse+N);
}

void process() {
    cost[0] = 0;
    for(int i = 1; i < N; i++) {
        cost[i] = muse[i].y - (muse[i].x - muse[i-1].x);
        //cout << cost[i] << endl;
    }
    psum[0] = 0;
    for(int i = 1; i < N; i++) {psum[i] = psum[i-1]+cost[i];}
}

void solve() {
    ll ans = 0;
    ll curm = psum[N-1];
    for(int i = N-1; i >= 0; i--) {
        curm = max(curm, psum[i]);
        ans = max(ans, curm-psum[i]+muse[i].y);
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    input();
    process();
    solve();
}

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