Submission #654266

#	Time	Username	Problem	Language	Result	Execution time	Memory
654266		hail	Art Exhibition (JOI18_art)	C++17	100 / 100	232 ms	19028 KiB

art

#include <bits/stdc++.h>
 
using namespace std;
 
#define vi vector<int>
#define vll vector<long long>
#define pb push_back
using ll= long long;
#define fast_io ios::sync_with_stdio(0); cin.tie(0)
#define inpint(x) int x; cin>>x
#define inpll(x) long long x; cin>>x
#define fl(i, n) for(int i=0; i<n; i++)
#define flo(i, n) for(int i=1; i<=n; i++)
#define int long long 
#define pi pair<int, int>
#define mp make_pair
#define ld long double

const int MOD = 7 + (int)1e9;
const int INF = (int)1e18;

//

void solve()
{
    int n;
    cin>>n;

    vector<pi> a(n+1);

    for(int i=1; i<=n; i++)
    {
        cin>>a[i].first>>a[i].second;
    }

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

    vector<int> s(n+1, 0);



    for(int i=1; i<=n; i++)
    {
        s[i] = s[i-1] + a[i].second;
    }


    int ans = s[1];
    //s_i - a_i - (s_(i-1) - a_i);
    int mv = -a[1].first;

    for(int i=2; i<=n; i++)
    {
        mv = min(mv, s[i-1] - a[i].first);
        int op = s[i] - a[i].first - mv;
        ans = max(ans, op);
    }

    cout<<ans;
}

signed main()
{
    fast_io;

    int t=1; 
    //cin>>t;
    while(t--)
    {
        solve();
    }
    cout<<endl;
}

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