제출 #350000

#제출 시각아이디문제언어결과실행 시간메모리
350000PulgsterArt Exhibition (JOI18_art)C++17
100 / 100
543 ms24928 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
    sim > struct rge { c b, e; };
    sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
    sim > auto dud(c* x) -> decltype(cerr << *x, 0);
    sim > char dud(...);
    struct debug {
#ifdef LOCAL
        ~debug() { cerr << endl; }
        eni(!=) cerr << boolalpha << i; ris; }
        eni(==) ris << range(begin(i), end(i)); }
        sim, class b dor(pair < b, c > d) {
            ris << "(" << d.first << ", " << d.second << ")";
        }
        sim dor(rge<c> d) {
            *this << "[";
            for (auto it = d.b; it != d.e; ++it)
                *this << ", " + 2 * (it == d.b) << *it;
            ris << "]";
        }
#else
        sim dor(const c&) { ris; }
#endif
    };
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define pb push_back
#define pii pair<int, int> 
#define pll pair<ll, ll>
#define vi vector<int>
#define vec vector
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
    void read(vector<ll> &a){
        for(ll &i : a) cin >> i;
    }
void read(vector<int> &a){
    for(int &i : a) cin >> i;
}ll INF = 1e18;
int mod = 1e9+7;

long long fastpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
vector<int> pow2(25);
const int maxn = 1e6+6;
const int maxk = 10;

void test_case(int tnum){
   int n;
    cin >> n;
    vector<pair<ll, ll>> a;
    for(int i = 0; i < n; i++){
        ll sz, p;
        cin >> sz >> p;
        a.pb({sz, p});
    }
    sort(a.begin(), a.end());
    vector<ll> pref(n+1);
    pref[0] = 0;
    for(int i = 1; i <= n; i++){
        pref[i] = pref[i-1] + a[i-1].second;
    }
    ll best = -INF;
    ll ans = -INF;
    for(int i = 0; i < n; i++){
        best = max(best, a[i].first - pref[i]);
        ans = max(ans, pref[i+1] + best - a[i].first);
        // debug() << imie(best);
    }
    cout << ans << '\n';
}

int main(void){
    cin.tie(0);
    int t = 1;
    // cin >>t;
    for(int test = 1; test <= t; test++){
        // cout << "Case #" << test << ": ";
        test_case(test);
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...