제출 #1278607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278607		IBory	Art Exhibition (JOI18_art)	C++20	100 / 100	125 ms	12108 KiB

art

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 500005;
pii P[MAX];
ll dp[MAX];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		ll a, b;
		cin >> a >> b;
		P[i] = { a, b };
	}
	sort(P, P + N + 1);
	ll cur = 0, ans = 0;
	for (int i = N; i > 0; --i) {
		cur += P[i].second - P[i].first + P[i - 1].first;
		dp[i] = cur;
		cur = max(0LL, cur);
	}
	for (int i = 1; i <= N; ++i) {
		ans = max(ans, max(P[i].second, P[i].second + dp[i + 1]));
	}
	cout << ans;
	return 0;
}

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