이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 500000
using namespace std;
bool sortcol(vector<int> v1, vector<int> v2) {
return v1[0] < v2[0];
}
vector< vector<int> > vect;
int pre[MAXN];
int main() {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
int A, B;
cin >> A >> B;
vector<int> vals;
vals.push_back(A); vals.push_back(B);
vect.push_back(vals);
}
sort(vect.begin(), vect.end(), sortcol);
cout << endl;
int curr = 0;
for (int i = 0; i < N-1; i++) {
curr = max(curr, vect[i][1]);
pre[i] = curr;
curr += (vect[i][0] - vect[i+1][0] + vect[i+1][1]);
}
pre[N - 1] = max(curr, vect[N - 1][1]);
curr = 0;
int ans = 0;
for (int i = N-1; i >0; i--) {
curr = max(curr, vect[i][1]);
ans = max(ans, pre[i] + curr - vect[i][1]);
curr += (vect[i-1][0] - vect[i][0] + vect[i-1][1]);
}
ans = max(ans, vect[0][1]);
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |