Submission #678178

#	Time	Username	Problem	Language	Result	Execution time	Memory
678178		Webbly	Art Exhibition (JOI18_art)	C++17	0 / 100	1 ms	212 KiB

art

#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[500005];

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


*/

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