Submission #891893

#	Time	Username	Problem	Language	Result	Execution time	Memory
891893		goodspeed0208	Art Exhibition (JOI18_art)	C++14	100 / 100	291 ms	56372 KiB

art

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<utility>
#define int long long
#define INF 1000000000000000000
#define pii pair<long long, long long>
using namespace std;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<pii>v(n);
	for(int i = 0 ; i < n ; i++) cin >> v[i].first >> v[i].second;
	sort(v.begin(), v.end());
	vector<int>psum(n);
	psum[0] = v[0].second;
	for (int i = 1 ; i < n ; i++) psum[i] = psum[i-1] + v[i].second;
	
	int start = 0, end = n-1;
	set<pii>st;
	st.insert({0, n-1});
	for (int i = n-2 ; i >= 0 ; i--) {
		int t = (v[n-1].first - v[i].first) - (psum[n-1] - psum[i]);
		st.insert({t, i});
		/*if (v[n-1].first - v[i].first > psum[n-1] - psum[i]) end = i;
		cout << v[n-1].first - v[i].first << " " << psum[n-1] - psum[i] << " ";
		cout << end << "\n";*/
	}
	
	int df = psum[n-1] - (v[n-1].first - v[0].first);
	int ans = 0;
	for (int i = 0 ; i < n ; i++) {
		pii p = *st.rbegin();
		ans = max(ans, df + p.first);
		//cout << df << " " << p.first<< "\n";
		int t = (v[n-1].first - v[i].first) - (psum[n-1] - psum[i]);
		st.erase({t, i});
		if (i < n-1) df = df - v[i].second + v[i+1].first - v[i].first;
		//if (v[i].first - v[0].first > psum[i]) start = i;
	}
	cout << ans << "\n";
	/*cout << "\n";
	if (end <= start) start = end = n-1;
	cout << start << " " << end << "\n";
	if (start == 0) cout << psum[end] - (v[end].first - v[start].first) << "\n";
	else cout << psum[end] - psum[start-1] - (v[end].first - v[start].first) << "\n";
	*/
	/*int ans = 0, start, end;
	for (int i = 0 ; i < n ; i++) {
		//cout << psum[i] << " ";
		for (int j = i ; j < n ; j++) {
			int t;
			if (i == 0) t = psum[j] - (v[j].first - v[i].first);
			else t = (psum[j] - psum[i-1]) - (v[j].first - v[i].first);
			if (t > ans) start = i, end = j;
			ans = max(ans, t);
		}
	}
	cout << start <<" " << end << "\n";
	cout << ans << "\n";*/
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:24:6: warning: unused variable 'start' [-Wunused-variable]
   24 |  int start = 0, end = n-1;
      |      ^~~~~
art.cpp:24:17: warning: unused variable 'end' [-Wunused-variable]
   24 |  int start = 0, end = n-1;
      |                 ^~~

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