제출 #678555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678555		tranxuanbach	Art Exhibition (JOI18_art)	C++17	100 / 100	223 ms	13992 KiB

art

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

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 5e5 + 5;

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

ll c[N];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n;
    ForE(i, 1, n){
        cin >> a[i].fi >> a[i].se;
    }
    sort(a + 1, a + n + 1);
    ForE(i, 1, n){
        b[i] = b[i - 1] + a[i].se;
    }

    ll ans = 0, val = numeric_limits <ll>::min();
    ForE(i, 1, n){
        val = max(val, a[i].fi - b[i - 1]);
        ans = max(ans, b[i] - a[i].fi + val);
    }
    cout << ans << endl;
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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