Submission #1109259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109259		ind1v	Art Exhibition (JOI18_art)	C++11	100 / 100	156 ms	11852 KiB

art

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

int n;
long long a[N];
int b[N];
int ord[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
  }
  iota(ord + 1, ord + n + 1, 1);
  sort(ord + 1, ord + n + 1, [](const int &u, const int &v) -> bool {
    return a[u] < a[v];
  });
  long long ans = numeric_limits<long long>::min();
  long long pb = 0;
  long long mx = numeric_limits<long long>::min();
  for (int i = 1; i <= n; i++) {
    mx = max(mx, a[ord[i]] - pb);
    ans = max(ans, pb + b[ord[i]] - a[ord[i]] + mx);
    pb += b[ord[i]];
  }
  cout << ans << '\n';
  return 0;
}

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