Submission #1244445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244445		greenbinjack	Art Exhibition (JOI18_art)	C++20	100 / 100	132 ms	12140 KiB

art

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
using LL = long long;
 
#define all(V) V.begin(), V.end()
 
template <typename DT> using ordered_set = tree <DT, null_type, less <DT>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename DT> using minheap = priority_queue < DT, vector <DT>, greater <DT> >;
template <class T> bool chMax (T &x, T y) { return y > x ? x = y, 1 : 0; }
template <class T> bool chMin (T &x, T y) { return y < x ? x = y, 1 : 0; }

const int N = 5E5 + 69;

LL a[N], pref[N];
int b[N], order[N];

int main() {
  cin.tie (nullptr) -> ios_base ::  sync_with_stdio (false);

  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];

  iota (order + 1, order + n + 1, 1);
  sort (order + 1, order + n + 1, [&] (int i, int j) {
    if (a[i] == a[j]) return b[i] < b[j];
    return a[i] < a[j];
  });

  for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + b[order[i]];

  LL mn = pref[0] - a[order[1]], ans = LLONG_MIN;
  for (int i = 1; i <= n; i++) {
    ans = max (ans, pref[i] - a[order[i]] - mn);
    mn = min (mn, pref[i] - a[order[i + 1]]);
  }

  cout << ans << '\n';

  return 0;   
} 

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