Submission #807463

#	Time	Username	Problem	Language	Result	Execution time	Memory
807463		OAleksa	Art Exhibition (JOI18_art)	C++14	100 / 100	152 ms	28632 KiB

art

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std; 

int main()
{
	  ios_base::sync_with_stdio(false);
	  cin.tie(0);
	  cout.tie(0);
	  int tt = 1;
		//cin >> tt;
	  while(tt--) {
			int n;
			cin >> n;
			vector<pair<long long, long long>> a(n);
			for(int i = 0;i < n;i++)
				cin >> a[i].f >> a[i].s;
			sort(a.begin(), a.end());
			vector<long long> d(n);
			for(int i = 1;i < n;i++)
				d[i] = a[i - 1].f - a[i].f + a[i].s;
			vector<long long> dp(n);
			long long ans = 0;
			for(int i = n - 2;i >= 0;i--) 
				dp[i] = max(0ll, dp[i + 1] + d[i + 1]);
			for(int i = 0;i < n;i++) 
				ans = max(ans, dp[i] + a[i].s);
			cout << ans;
		}
    return 0;
}

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