Submission #493940

#	Time	Username	Problem	Language	Result	Execution time	Memory
493940		ahmeteren	Art Exhibition (JOI18_art)	C++17	100 / 100	223 ms	24760 KiB

art

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
const int N = 1e5 + 5;
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	// #ifndef ONLINE_JUDGE
	// 	freopen("in.txt", "r", stdin);
	// 	freopen("out.txt", "w", stdout);
	// #endif
 
	ll n;
	cin >> n;
 
	vector<pair<ll, ll>> vec(n + 1);
	vector<ll> prefix(n + 1);
 
	for(int i = 1; i <= n; i++)
		cin >> vec[i].first >> vec[i].second;
 
	sort(vec.begin() + 1, vec.end());
 
	for(int i = 1; i <= n; i++)
	{
		prefix[i] = prefix[i - 1];
		prefix[i] += vec[i].second;
	}

	ll l = 1, mn = vec[1].first, cevap = vec[1].second;
 
	for(int r = 2; r <= n; r++)
	{
		while(l < r and vec[r].first - mn > prefix[r - 1] - prefix[l - 1])
		{
			l++;
			mn = vec[l].first;
		}

		cevap = max(cevap, (prefix[r] - prefix[l - 1]) - (vec[r].first - mn));
	}

	cout << cevap << '\n';
	return 0;
}

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