# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1099306 | LilPluton | Art Exhibition (JOI18_art) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool umax(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool umin(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
const int sz = 1e6 + 5;
#define int long long
struct DSU{
vector<int>e;
DSU(int n){
e.assign(n + 1, -1);
}
int _find(int v){
if(e[v] < 0){
return v;
}
return e[v] = _find(e[v]);
}
int _union(int u,int v){
u = _find(u);
v = _find(v);
if(u != v){
if(e[u] > e[v]){
swap(u, v);
}
e[u] += e[v];
e[v] = u;
return 1;
}
return 0;
}
};
void test_case(int testcase){
int n;
cin >> n;
vector<pair<int,int>>a(n + 1);
vector<int>p(n + 1, 0);
for(int i = 1; i <= n; ++i){
cin >> a[i].first >> a[i].second;
}
sort(begin(a), end(a));
ll mx = LLONG_MIN, res = LLONG_MIN;
for(int i = 1; i <= n;++i){
umax(mx, a[i].first - p[i - 1]);
p[i] = p[i - 1] + a[i].second;
umax(res, p[i] - a[i].first + mx);
}
cout << res << endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
for(int test = 1; test <= T; ++test){
test_case(test);
}
}
/*
*/