Submission #521882

#	Time	Username	Problem	Language	Result	Execution time	Memory
521882		Monarchuwu	Art Exhibition (JOI18_art)	C++17	100 / 100	216 ms	13644 KiB

art

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

typedef pair<ll, int> pli;
#define ff first
#define ss second

const int N = 5e5 + 5;
int n;
pli a[N];

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].ff >> a[i].ss;
    sort(a + 1, a + n + 1);

    //   S - (Amax - Amin)
    // = sum[r] - sum[l - 1] - (A[r] - A[l])
    // = (sum[r] - A[r]) + (A[l] - sum[l - 1])
    ll ans(0), sum(0), prf(0);
    for (int i = 1; i <= n; ++i) {
        prf = max(prf, a[i].ff - sum);
        sum += a[i].ss;
        ans = max(ans, sum - a[i].ff + prf);
    }
    cout << ans << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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