Submission #520635

#	Time	Username	Problem	Language	Result	Execution time	Memory
520635		emon_2007	Art Exhibition (JOI18_art)	C++17	100 / 100	187 ms	21920 KiB

art

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;
pair <ll, ll> a[N];
ll b[N];
void solve() 
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i].first >> a[i].second;
    }
    sort(a, a + n);
    for(int i = 0; i < n; i++)
    {
        b[i + 1] = b[i] + a[i].second;
    }
    ll m = a[0].first;
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        m = max(m, a[i].first - b[i]);
		ans = max(ans, m + b[i + 1] - a[i].first);
    }
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

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