Submission #1334469

#TimeUsernameProblemLanguageResultExecution timeMemory
1334469zhehanArt Exhibition (JOI18_art)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int, int> ii;

signed main() {
  int n = 0;
  cin >> n;
  vector<ii> art(n, ii(0, 0));
  for (int i = 0; i < n; ++i) {
    cin >> art[i].first >> art[i].second;
  }
  sort(art.begin(), art.end());
  vector<int> prefixval(n, 0);
  prefixval[0] = art[0].second;
  for (int i = 1; i < n; ++i) {
    prefixval[i] = prefixval[i - 1] + art[i].second;
  }
  int l = 0, maxval = 0, val = 0;
  for (int i = 0; i < n; ++i) {
    if (l == 0) {
      val = prefixval[i] - art[i].first + art[l].first;
    } else {
      val = prefixval[i] - prefixval[l - 1] - art[i].first + art[l].first;
    }
    while (val < 0) {
      l++;
      val = prefixval[i] - prefixval[l - 1] - art[i].first + art[l].first;
    }
    maxval = max(maxval, val);
  }
  cout << maxval << '\n';
  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...