Submission #843930

#	Time	Username	Problem	Language	Result	Execution time	Memory
843930		Elvin_Fritl	Art Exhibition (JOI18_art)	C++17	100 / 100	403 ms	24904 KiB

art

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+55;
const long long inf = 1e16+66;

int32_t main()
{
    int n;
    cin>>n;
    vector<pair<long long,long long>>v(n);
    for(int i = 0; i < n; i++){
    	cin>>v[i].first>>v[i].second;
    }
    sort(v.begin() , v.end());
    reverse(v.begin() , v.end());
    long long pre[n+1];
    pre[0] = 0;
    for(int i=1;i<=n;i++){
        pre[i] = pre[i-1] + v[i - 1].second;
    }
    long long mini = inf , res = 0;
    for(int i=1;i<=n;i++){
    	mini=min(mini,pre[i-1] + v[i - 1].first);
    	res=max(res,pre[i] + v[i - 1].first - mini);
    }
    cout << res;

    return 0;
}
/*

1 1    2 2    3 3    4 4
1


*/

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