Submission #225189

#	Time	Username	Problem	Language	Result	Execution time	Memory
225189		muhammad_hokimiyon	Art Exhibition (JOI18_art)	C++14	100 / 100	407 ms	50284 KiB

art

#include <bits/stdc++.h>

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#pragma GCC optimize("Ofast")
//1.0 * clock() / CLOCKS_PER_SEC

#define fi first
#define se second
#define ll long long
#define dl double long

using namespace std;

const ll NN = 1e10 + 7;
const int N = 5e5 + 7;
const int M = 6;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;
const int B = sqrt(N);

int n;
ll a[N];
ll b[N];
ll sum[N];

void solve1()
{
    cin >> n;
    vector < int > v;
    for( int i = 1; i <= n; i++ ){
        cin >> a[i] >> b[i];
        v.push_back(i);
    }
    sort( v.begin() , v.end() , [&] ( int i , int j ){
        return a[i] < a[j];
    } );
    set < ll > s;
    for( int h = 1; h <= n; h++ ){
        int i = v[h - 1];
        sum[h] = sum[h - 1] + b[i];
    }
    ll ans = -1e18;
    for( int h = 1; h <= n; h++ ){
        int i = v[h - 1];
        s.insert( sum[h - 1] - a[i] );
        auto x = *s.begin();
        ans = max( ans , sum[h] - a[i] - x );
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int cghf = 1;//cin >> cghf;
    while( cghf-- ){
        solve1();
    }
}

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