Submission #749328

#TimeUsernameProblemLanguageResultExecution timeMemory
749328tch1cherinArt Exhibition (JOI18_art)C++17
100 / 100
571 ms31140 KiB
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

int main() {
  int N;
  cin >> N;
  vector<long long> A(N), B(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
  }
  vector<int> order(N);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return A[i] < A[j];
  });
  vector<long long> C;
  for (int i = 0; i < N; i++) {
    C.push_back(B[order[i]]);
    if (i < N - 1) {
      C.push_back(A[order[i]] - A[order[i + 1]]);
    } 
  }
  long long Min[2] = {0, INF}, sum = 0, ans = 0;
  for (int i = 0; i < 2 * N - 1; i++) {
    sum += C[i];
    ans = max(ans, sum - Min[i % 2]);
    Min[(i + 1) % 2] = min(Min[(i + 1) % 2], sum);
  }
  cout << ans << "\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...