Submission #753470

#	Time	Username	Problem	Language	Result	Execution time	Memory
753470		IvanJ	Art Exhibition (JOI18_art)	C++17	100 / 100	223 ms	32676 KiB

art

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 5e5 + 5;

int n;
ll c[maxn];
ll pref[maxn];
ll maxi[maxn];

int main() {
	scanf("%d", &n);
	vector<pair<ll, int>> v;
	for(int i = 0;i < n;i++) {
		ll a;int b;
		scanf("%lld%d", &a, &b);
		v.pb({a, b});	
	}
	
	sort(all(v));
	for(int i = 0;i < n;i++) {
		c[i] = (ll)v[i].y - v[i].x;
		if(i) c[i] += v[i - 1].x;
		else c[i] += v[i].x;
	}
	
	pref[0] = c[0];
	for(int i = 1;i < n;i++)
		pref[i] = pref[i - 1] + c[i];
	
	maxi[n - 1] = pref[n - 1];
	for(int i = n - 2;i >= 0;i--) 
		maxi[i] = max(maxi[i + 1], pref[i]);
	
	ll ans = 0;
	for(int i = 0;i < n;i++) {
		ll sol = maxi[i];
		if(i) sol -= pref[i - 1];
		if(i) sol += v[i].x - v[i - 1].x;
		ans = max(ans, sol);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
art.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%lld%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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