Submission #678041

#TimeUsernameProblemLanguageResultExecution timeMemory
678041vjudge1Art Exhibition (JOI18_art)C++14
0 / 100
0 ms212 KiB
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long

using namespace std;

ll binpow (ll a, ll b){
    if (b == 0) return 1;
    if (b & 1) return binpow(a, b - 1) * a;
    else return binpow(a, b / 2) * binpow(a, b / 2);
}
ll gcd(ll a, ll b){
    return (b ? gcd(b, a % b) : a);
}
ll nums(ll g){
    ll cur = 0;
    while(g){
        cur++, g /= 10;
    }

    return cur;
}

bool comp(pair <ll, ll> a, pair <ll, ll> b){
    if (a.first == b.first){
        return a.second < b.second;
    }

    else return a.first < b.first;
}

ll get1(ll q, ll g){
    ll cur = 1;

    for (ll i = q; i > g; i--){
        cur *= i;
    }

    return cur;
}

const ll mod = (ll)998244353;

ll n, k, x, y;

pair <ll, ll> p[200005];

vector <ll> v;

bool used[100][5];

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    cin >> n;

    for (ll i = 1; i <= n; i++){
        cin >> x >> y;

        p[i] = {x, y};
    }

    sort (p + 1, p + n + 1, comp);

    ll pref[n + 1];

    pref[0] = 0;

    for (ll i = 1; i <= n; i++){
        pref[i] = pref[i - 1] + p[i].second;
    }

    ll l = 1, r = n, mx = (ll)-1e15;

    while(l <= r){
        mx = max(mx, (pref[r] - pref[l - 1]) - (p[r].first - p[l].first));

        if ((pref[r - 1] - pref[l - 1]) - (p[r - 1].first - p[l].first) >= (pref[r] - pref[l]) - (p[r].first - p[l + 1].first)){
            r--;
        }

        else l++;
    }

    cout << mx;

    return 0;
}

/**

6
4 1
1 5
10 3
9 1
4 2
5 3

1 5
4 1
4 2
5 3
9 1
10 3

6
4
7


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