Submission #644523

#	Time	Username	Problem	Language	Result	Execution time	Memory
644523		tvladm2009	Art Exhibition (JOI18_art)	C++14	100 / 100	178 ms	24728 KiB

art

#include <bits/stdc++.h>

using ll = long long;

const int nmax = 500000;

std::pair<ll, ll> a[1 + nmax];
ll sp[1 + nmax];

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);

  int n;
  std::cin >> n;
  for(int i = 1; i <= n; i++)
    std::cin >> a[i].first >> a[i].second;

  std::sort(a + 1, a + n + 1, [&](const std::pair<ll, ll> &a, const std::pair<ll, ll> &b) -> bool {
    return a.first < b.first;
  });

  for(int i = 1; i <= n; i++)
    sp[i] = sp[i - 1] + a[i].second;
  ll mn = (1LL << 60), mx = -(1LL << 60);
  for(int i = 1; i <= n; i++) {
    mn = std::min(mn, sp[i - 1] - a[i].first);
    mx = std::max(mx, sp[i] - a[i].first - mn);
  }
  std::cout << mx;
  return 0;
}

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