Submission #978023

#TimeUsernameProblemLanguageResultExecution timeMemory
978023kilkuwuArt Exhibition (JOI18_art)C++17
100 / 100
143 ms24888 KiB
#include <bits/stdc++.h>

#define nl '\n'

const int mxN = 5e5 + 5;
int N;
std::pair<int64_t, int64_t> a[mxN];
int64_t pref[mxN];

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  std::cin >> N;

  for (int i = 0; i < N; i++) {
    std::cin >> a[i].first >> a[i].second;
  }

  std::sort(a, a + N);
  /*
  
*/

  for (int i = 0; i < N; i++) {
    pref[i + 1] = pref[i] + a[i].second;
  }

  // maximize pref[i + 1] - pref[j] - (a[i].first - a[j].second)
  // pref[i + 1] - a[i].first - pref[j] + a[j].second


  int64_t maximal = -1e18;
  int64_t ans = maximal;
  for (int i = 0; i < N; i++) {
    maximal = std::max(maximal, a[i].first - pref[i]); 

    ans = std::max(ans, pref[i + 1] - a[i].first + maximal);
  }

  std::cout << ans << nl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...