Submission #1071329

#TimeUsernameProblemLanguageResultExecution timeMemory
1071329vjudge1Art Exhibition (JOI18_art)C++17
30 / 100
45 ms2396 KiB
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

const int N = 5e5 + 11;
pair<int, int> a[N];
int pref[N];
int cost(int i, int j) {
    int sum = pref[j] - pref[i - 1];
    int mx = a[j].fi, mn = a[i].fi;
    return sum - (mx - mn);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        cin>>a[i].fi>>a[i].se;
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++){
        pref[i] = pref[i - 1] + a[i].se;
    }
    int res = 0;
    for(int i = 1; i <= n; i++){
        int l = i, r = n, ans = 0;
        for(int j = 1; j <= 1000; j++){
            int m1 = l + (r - l) / 3;
            int m2 = r - (r - l) / 3;
            ans = max({ans, cost(i, m1), cost(i, m2)});
            if(cost(i, m1) > cost(i, m2))l = m1;
            else r = m2;
        }
        for(int j = -500; j <= 500; j++){
            if((l + j) >= i && (l + j) <= n) {
                if(cost(i, l + j) > ans)ans = cost(i, l + j);
            }
        }
        res = max(res, ans);
    }
    cout << res << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...