Submission #1331295

#TimeUsernameProblemLanguageResultExecution timeMemory
1331295lywoemArt Exhibition (JOI18_art)C++20
0 / 100
0 ms344 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define l(a, b, i) for (ll i = a; i < b; i++)
#define rl(a, b, i) for (ll i = a; i >= b; i--)
#define vpair vector<pair<ll, ll>>
#define inf LLONG_MAX
#define ninf LLONG_MIN

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll N; cin >> N; vector<ll> sz(N + 1, 0), val(N + 1, 0); vector<pair<ll, ll>> vec(N + 1);
    l(1, N + 1, i) {
        cin >> sz[i] >> val[i];
        vec[i] = {sz[i], val[i]};
    }
    sort(vec.begin() + 1, vec.end()); // sort theo increasing size nhé

    //vector<ll> pre(N + 1, 0); // prefix cái val á   
    //l(1, N + 1, i) pre[i] = pre[i - 1] + vec[i].second;

    ll ans = 0;
    ll cursum = 0; // tổng các val của các artworks được chọn tính đến nay
    ll left = 1;
    l(1, N + 1, r) {
        cursum += vec[r].second;

        while (left < r && vec[left].second + (vec[r].first - vec[left + 1].first) <= vec[r].first - vec[left].first) { // cái val của vec[l] k đủ để bù đắp cho cái sự khoảng cách về sz T_T
            cursum -= vec[left].second;
            left++;
        }

        ans = max(ans, cursum - (vec[r].first - vec[left].first));
    }

    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...