제출 #1241375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241375		Nailuj_217	Art Exhibition (JOI18_art)	C++20	100 / 100	349 ms	12136 KiB

art

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll LEN = 500005;

struct Sub {
    ll left;
    ll right;
    ll full;
    ll best;
    Sub() {}
    Sub(ll s) : Sub(s, s, s, s) {}
    Sub(ll left, ll right, ll full, ll best) : left(left), right(right), full(full), best(best) {}
};

array<pair<ll, ll>, LEN> artworks;
array<ll, LEN> prefb;

Sub build(ll s, ll f) {
    if (s == f) return Sub(artworks[s].second);
    Sub l = build(s, (s+f)/2);
    Sub r = build((s+f)/2+1, f);
    Sub ret = Sub();
    // left
    // ) left.left , left.full + r.left
    ret.left = max(l.left, l.full + r.left - (artworks[(s+f)/2+1].first - artworks[(s+f)/2].first));
    ret.right = max(r.right, r.full + l.right - (artworks[(s+f)/2+1].first - artworks[(s+f)/2].first));
    ret.full = prefb[f] - prefb[s-1] - (artworks[f].first - artworks[s].first);
    ret.best = max({
        l.best,
        r.best,
        l.right + r.left - (artworks[(s+f)/2+1].first - artworks[(s+f)/2].first)
    });
    return ret;
}





int main() {

    // freopen("input.in", "r", stdin);

    ll n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> artworks[i].first >> artworks[i].second;
    }
    sort(&artworks[1], &artworks[n+1]);

    for (int i = 1; i <= n; i++) {
        prefb[i] = prefb[i-1] + artworks[i].second;
    }
    
    cout << build(1, n).best << endl;



    return 0;
}

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