Submission #470661

#	Time	Username	Problem	Language	Result	Execution time	Memory
470661		PiejanVDC	Art Exhibition (JOI18_art)	C++17	100 / 100	637 ms	36816 KiB

art

#include <bits/stdc++.h>
using namespace std;

signed main() {
	int n; cin>>n;
	vector<pair<long long,long long>>vv(n);
	for(auto &z : vv)
		cin >> z.first >> z.second;
	sort(vv.begin(),vv.end());
	vv.push_back({-1,0});
	vector<pair<long long,long long>>v;
	long long ele = vv[0].first;
	long long curr = 0;
	for(int i = 0 ; i <= n ; i++) {
		if(vv[i].first != ele)
			v.push_back({ele,curr}),curr=0,ele=vv[i].first;
		curr+=vv[i].second;
	}
	long long profit = 0;
	long long ans = 0;
	for(int i = 0 ; i < (int)v.size() ; i++) {
		profit+=v[i].second;
		if(i > 0) profit-=(v[i].first-v[i-1].first);
		profit=max(profit,v[i].second);
		ans=max(ans,profit);
	}
	cout << ans;
}

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