Submission #1317847

#TimeUsernameProblemLanguageResultExecution timeMemory
1317847_nothing_Art Exhibition (JOI18_art)C++17
0 / 100
0 ms332 KiB
/**
  S - (a_max - a_min) = pre_b(j) - a(j) - (pre_b(i - 1) - a(i))
**/

#include <bits/stdc++.h>
using namespace std;

int n;

struct Data {
  long long size, value;

  bool operator < (const Data &other) const {
    return (size < other.size);
  }
};

#define MAX_N 500500
Data d[MAX_N];

int main() {
  ios_base::sync_with_stdio(false);cin.tie(nullptr);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> d[i].size >> d[i].value;

  sort(d + 1, d + 1 + n);

  for (int i = 1; i <= n; ++i) d[i].value += d[i - 1].value;

  long long ans = 0, pref = d[1].size;
  for (int i = 1; i <= n; ++i) {
    ans = max(ans, d[i].value - d[i].size - pref);
    pref = min(pref, d[i - 1].value - d[i].size);
  }

  cout << ans;

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...