Submission #763901

#	Time	Username	Problem	Language	Result	Execution time	Memory
763901		ind1v	Art Exhibition (JOI18_art)	C++11	100 / 100	170 ms	24704 KiB

art

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;

int n;
long long a[N];
int b[N];
long long p[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, [](int &i, int &j) -> bool {
    return a[i] < a[j];
  });
  for (int i = 1; i <= n; i++) {
    p[i] = b[ord[i]] + p[i - 1];
  }
  long long mx = numeric_limits<long long>::min();
  long long ans = numeric_limits<long long>::min();
  for (int i = 1; i <= n; i++) {
    mx = max(mx, a[ord[i]] - p[i - 1]);
    ans = max(ans, p[i] - a[ord[i]] + mx);
  }
  cout << ans;
  return 0;
}

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