Submission #749328

#	Time	Username	Problem	Language	Result	Execution time	Memory
749328		tch1cherin	Art Exhibition (JOI18_art)	C++17	100 / 100	571 ms	31140 KiB

art

#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";
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50