제출 #493940

#제출 시각아이디문제언어결과실행 시간메모리
493940ahmeterenArt Exhibition (JOI18_art)C++17
100 / 100
223 ms24760 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...