제출 #146448

#제출 시각아이디문제언어결과실행 시간메모리
146448MathStudent2002Art Exhibition (JOI18_art)C++14
100 / 100
268 ms28660 KiB
//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();
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...