제출 #735880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
735880		That_Salamander	Art Exhibition (JOI18_art)	C++17	0 / 100	1 ms	340 KiB

art

#include <bits/stdc++.h>
#define int long long

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

int n;
pii art[500000];
int value[500000], prefix[500000], midx[500000];
int cp[500001];

int getRes(int l, int r) {
    return cp[r+1] - cp[l] - art[r].first + art[l].first;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    FOR(i, n) {
        cin >> art[i].first >> art[i].second;
    }

    sort(art, art + n);

    FOR (i, n) {
        cp[i + 1] = cp[i] + art[i].second;
    }

    value[0] = 0;

    FORB(i, 1, n) {
        value[i] = art[i].second - (art[i].first - art[i-1].first);
        prefix[i] = prefix[i - 1] + value[i];
    }

    int maxIdx = -1;
    FORR(i, n) {
        midx[i] = maxIdx;
        if (maxIdx == -1 || prefix[i] > prefix[maxIdx]) {
            maxIdx = i;
        }
    }

    int res = 0;

    FOR(i, n - 1) {
        res = max(res, getRes(i, midx[i]));
        //cout << i << " " << midx[i] << " " << res << endl;
    }

    cout << res << endl;
}

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