Submission #1089993

#TimeUsernameProblemLanguageResultExecution timeMemory
1089993HienTDArt Exhibition (JOI18_art)C++14
100 / 100
148 ms20948 KiB
#include <bits/stdc++.h>
using namespace std;

//#define LOCAL

#define          	fi  first
#define             se  second
#define           TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define         ALL(v)  (v).begin(), (v).end()
#define  		BIT(x)  (1LL << (x))
#define 	MASK(x, i)  (((x) >> (i)) & 1)
#define   FOR(i, a, b)  for(int i = (a), _b = (b); i <= _b; ++ i)
#define  FORD(i, b, a)  for(int i = (b), _a = (a); i >= _a; -- i)

const string NAME = "BAITAP";

const long long INF = 1e18;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int mod = 998244353;

const int mxN = 5e5 + 5;

int N;
vector<pair<long long, long long>> A(mxN);

void init(void){
	cin >> N;
	FOR(i, 1, N) cin >> A[i].fi >> A[i].se;
}

struct cmp{
	bool operator() (const pair<long long, long long> &a, const pair<long long, long long> &b){
		return a.fi != b.fi ? a.fi < b.fi : a.se > b.se;
	}
};

void process(void){
	sort(A.begin() + 1, A.begin() + 1 + N, cmp());
	long long ans = -INF;
	long long mx = -INF;
	FOR(i, 1, N){
		A[i].se += A[i - 1].se;
		mx = max(A[i].fi - A[i - 1].se, mx);
		ans = max(ans, A[i].se - A[i].fi + mx);
	}
	cout << ans;
}

signed main(void){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	#ifdef LOCAL
		freopen((NAME + ".INP").c_str(), "r", stdin);
		freopen((NAME + ".OUT").c_str(), "w", stdout);
	#endif // I/O

	init();
	process();
	cerr << "\nTime elapsed: " << TIME << "s.\n";
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...