제출 #642214

#제출 시각아이디문제언어결과실행 시간메모리
642214as111Art Exhibition (JOI18_art)C++14
50 / 100
1088 ms40304 KiB
#include <iostream> #include <vector> #include <algorithm> #define MAXN 500000 using namespace std; bool sortcol(vector<long long> v1, vector<long long> v2) { return v1[0] < v2[0]; } vector< vector<long long> > vect; long long pre[MAXN]; int main() { int N; cin >> N; for (int i = 0; i < N; i++) { long long A, B; cin >> A >> B; vector<long long> vals; vals.push_back(A); vals.push_back(B); vect.push_back(vals); } sort(vect.begin(), vect.end(), sortcol); long long 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; long long 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...