제출 #259834

#제출 시각아이디문제언어결과실행 시간메모리
259834shivensinha4Art Exhibition (JOI18_art)C++17
100 / 100
254 ms24864 KiB
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
#define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'


int main() {
	#ifndef ONLINE_JUDGE
	//freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin >> n;
	vector<pair<ll, ll>> nums(n); // size, val
	for_(i, 0, n) cin >> nums[i].first >> nums[i].second;
	sort(nums.begin(), nums.end());
	
	vector<ll> dp(n);
	dp[n-1] = nums[n-1].second - nums[n-1].first;
	for (int i = n-2; i >= 0; i--) {
		dp[i] = max(nums[i].second - nums[i].first, nums[i].second + dp[i+1]);
	}
	
	ll ans = 0;
	for_(i, 0, n) ans = max(ans, dp[i]+nums[i].first);
	cout << ans << endl;

	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...