Submission #1179721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179721		patgra	Art Exhibition (JOI18_art)	C++20	50 / 100	1098 ms	79856 KiB

art

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    map<ll, ll> mappy, prefSum, maxSuf;
    rep(i, 0, n) {
        ll x, y;
        cin >> x >> y;
        mappy[x] += y;
    }
    ll prv = 0;
    repIn2(k, v, mappy) prv += v, prefSum[k] = prv;
    prv = -5e18;
    rep(it, mappy.rbegin(), mappy.rend()) {
        auto k = it -> first;
        prv = max(prv, prefSum[k] - k);
        maxSuf[k] = prv;
        DC << "maxSuf[" << k << "] = " << prv << eol;
    }
    ll ans = -5e18;
    prv = 0;
    repIn2(k, v, mappy) {
        DC << ' ' << k << ' ' << prv + k + maxSuf[k] << eol;
        ans = max(ans, prv + k + maxSuf[k]);
        prv = -prefSum[k];
    }
    cout << ans << '\n';
}

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