Submission #547860

#	Time	Username	Problem	Language	Result	Execution time	Memory
547860		beaconmc	Art Exhibition (JOI18_art)	C++17	100 / 100	370 ms	40400 KiB

art

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


int main(){
    fast();
    ll n; cin >> n;
    vector<vector<ll>> paintings;

    FOR(i,0,n){
        ll a,b;
        cin >> a >> b; 
        paintings.push_back({a,b});
    }
    sort(paintings.begin(), paintings.end());
    ll curmax=-1, curmin=1000000000000000000, cur=0, ans=0;
    FOR(i,0,n){
        curmax = max(curmax, paintings[i][0]);
        curmin = min(curmin, paintings[i][0]);
        cur += paintings[i][1];
        if (cur-(curmax-curmin)<paintings[i][1]){
            curmax = paintings[i][0];
            curmin = paintings[i][0];
            cur = paintings[i][1];
        }
        ans = max(ans, cur-(curmax-curmin));
    }
    cout << ans;
}

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