제출 #1071313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071313		vjudge1	Art Exhibition (JOI18_art)	C++17	50 / 100	1042 ms	12112 KiB

art

#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 = -1000; j <= 1000; 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';
}

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