Submission #349992

#TimeUsernameProblemLanguageResultExecution timeMemory
349992PulgsterArt Exhibition (JOI18_art)C++17
0 / 100
1 ms364 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;
}int INF = 1e9;
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;
}

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());
    // debug() << imie(a);
    int l, r;
    l = r = 0;
    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 ans = 0;
    l = 0;
    r = 0;
    // debug() << imie(pos) imie(best);
    while(r < n){
        ll val = pref[r+1] - pref[l];
        ll sub = a[r].first - a[l].first;
        ans = max(ans, val-sub);
        if(l != r && val - a[l].second - (a[r].first - a[l+1].first) > val-sub){
            l++;
        } else{
            r++;
        }
    }
    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...