제출 #992055

#제출 시각아이디문제언어결과실행 시간메모리
992055coolboy19521Art Exhibition (JOI18_art)C++17
0 / 100
0 ms348 KiB
#include<bits/stdc++.h>

#define int unsigned long long

using namespace std;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    cin >> n;

    vector <array <int, 2>> v(n);

    for (auto& e : v) {
        cin >> e[0] >> e[1];
    }

    sort(begin(v), end(v));

    vector <array <int, 2>> r;
    int sm = v[0][1];

    for (int i = 1; i < n; i ++) {
        if (v[i][0] != v[i - 1][0]) {
            r.push_back({v[i - 1][0], sm});
            sm = v[i][1];
        } else {
            sm += v[i][1];
        }
    }

    r.push_back({v.back()[0], sm});
    int m = r.size();

    int le, ri, mx, it, in;
    le = ri = mx = sm = 0;

    for (; ri < m; ri ++) {
        mx = max(mx, r[ri][1]);
        sm += r[ri][1];
        it = sm - r[ri][0] + r[le][0];
        if (le < ri - 1) {
            in = sm - r[le][1] - r[ri][0] + r[le + 1][0];
        } else {
            in = 0;
        }
        for (; it < in && le < ri - 1; le ++) {
            sm -= r[le][1];
            it = sm - r[ri][0] + r[le][0];
            in = sm - r[le][1] - r[ri][0] + r[le + 1][0];
        }
        mx = max(mx, sm - (r[ri][0] - r[le][0]));
    }

    cout << mx << '\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...