제출 #807463

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