Submission #1184707

#TimeUsernameProblemLanguageResultExecution timeMemory
1184707versesrevArt Exhibition (JOI18_art)C++20
100 / 100
327 ms8244 KiB
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  int n;
  std::cin >> n;
  std::vector<std::pair<long long, long long>> arts(n);
  for (auto& [a, b] : arts) std::cin >> a >> b;
  std::ranges::sort(arts);
  
  long long ans = 0;
  long long b_sum = 0;
  long long min_diff = -arts[0].first;
  for (int i = 0; i < n; ++i) {
    // prefix sum i - prefix sum j-1 - arts[i].a + arts[j].a, j = 0 ~ i
    min_diff = std::min(min_diff, b_sum - arts[i].first);
    b_sum += arts[i].second;
    ans = std::max(ans, b_sum - arts[i].first - min_diff);
  }
  std::cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...