Submission #332357

#	Time	Username	Problem	Language	Result	Execution time	Memory
332357		limabeans	Art Exhibition (JOI18_art)	C++17	0 / 100	1 ms	364 KiB

art

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;
const ll inf = 1e18;



ll S[maxn], A[maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    int n;
    cin>>n;
    vector<pair<ll,ll>> a(n);
    for (int i=0; i<n; i++) {
	cin>>a[i].first>>a[i].second;
    }

    sort(a.begin(), a.end());

    for (int i=0; i<n; i++) {
	S[i+1] = S[i]+a[i].second;
	A[i+1] = a[i].first;
    }

    set<ll> st;


    ll hi = -inf;
    
    for (int i=1; i<=n; i++) {
	ll cur = S[i]-A[i];
	if (st.size()) {
	    cur += *st.rbegin();
	}
	hi = max(hi, cur);
	st.insert(A[i]-S[i-1]);
    }

    cout<<hi<<endl;
    
    return 0;
}

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