Submission #601188

#	Time	Username	Problem	Language	Result	Execution time	Memory
601188		jjiangly	Art Exhibition (JOI18_art)	C++14	50 / 100	19 ms	532 KiB

art

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define siz(x) int(x.size())
#define ll long long
#define ar array
#define vt vector
#define inf INT_MAX
#define lnf LLONG_MAX

const int nxm = int(5e3) + 7;

int n;
pair<ll, ll> a[nxm];

namespace sub3 {
  void solve() {
    sort(a, a + n);
    for (int i = 1; i < n; ++i) {
      a[i].second += a[i - 1].second;
    }
    ll ans = -lnf;
    for (int i = 0; i < n; ++i) {
      for (int j = i; j < n; ++j) {
        ans = max(ans, a[j].second - (i - 1 >= 0 ? a[i - 1].second : 0) - a[j].first + a[i].first);
      }
    }
    cout << ans << "\n";
  }
};

namespace sub4 {
  void solve() {
    sort(a, a + n);
    for (int i = 1; i < n; ++i) {
      a[i].second += a[i - 1].second;
    }
    ll ans = -lnf;
    ll prf = -lnf;
    for (int i = 0; i < n; ++i) {
      prf = max(prf, a[i].first - (i - 1 >= 0 ? a[i - 1].second : 0));
      ans = max(ans, a[i].second - a[i].first + prf);
    }
    cout << ans << "\n";
  }
};

int subtask() {
  if (n <= 5000) {
    return 3;
  }
  return 4;
};

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

  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i].first >> a[i].second;
  }
  if (subtask() == 3) {
    sub3::solve();
  } else {
    sub4::solve();
  }

  return 0;
}

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