Submission #166055

#	Time	Username	Problem	Language	Result	Execution time	Memory
166055		davooddkareshki	Art Exhibition (JOI18_art)	C++17	100 / 100	284 ms	32852 KiB

art

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define F first
#define S second

const int maxn = 1e6+10;
const int mod = 1e9+7;

int n, k;
ll a[maxn], b[maxn], pre[maxn];
vector<pair<ll,ll>> ve;

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

    cin>> n;
    for(int i = 1; i <= n; i++){
        cin>> a[i] >> b[i];
        ve.push_back({a[i],b[i]});
    }
    
    sort(ve.begin(), ve.end());

    ll mx = 0, ans = 0;
    for(int i = 0; i < n; i++)
    {
        pre[i] = pre[i-1] + ve[i].S;
        mx = max(mx, ve[i].F - pre[i-1]);
        ans = max(ans, pre[i] - ve[i].F + mx);
    }
    cout<< ans;
}

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