Submission #259834

#	Time	Username	Problem	Language	Result	Execution time	Memory
259834		shivensinha4	Art Exhibition (JOI18_art)	C++17	100 / 100	254 ms	24864 KiB

art

#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;
}

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