Submission #601064

#	Time	Username	Problem	Language	Result	Execution time	Memory
601064		jjiangly	Art Exhibition (JOI18_art)	C++14	0 / 100	15 ms	340 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(2e5) + 7;

struct cush {
  size_t operator()(uint64_t x) const {
    static const uint64_t f = chrono::steady_clock::now().time_since_epoch().count();
    x ^= f;
    return x ^ (x >> 16);
  }
};

int n;
ll a[nxm], b[nxm];
unordered_map<ll, int, cush> ump;

namespace sub3 {
  ll bit[nxm];
  void add(int x, ll v) {
    for (int i = x + 1; i <= nxm; i += i & -i) {
      bit[i - 1] += v;
    }
  }
  ll get(int x) {
    ll r = 0;
    for (int i = x; i > 0; i -= i & -i) {
      r += bit[i - 1];
    }
    return r;
  }
  void solve() {
    vt<ll> zp;
    for (int i = 0; i < n; ++i) {
      zp.push_back(a[i]);
    }
    sort(all(zp));
    zp.erase(unique(all(zp)), zp.end());
    for (int i = 0; i < siz(zp); ++i) {
      ump[zp[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
      add(ump[a[i]], b[i]);
    }
    ll ans = -lnf;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        int mx = max(ump[a[i]], ump[a[j]]);
        int mn = min(ump[a[i]], ump[a[j]]);
        ans = max(ans, get(mx + 1) - get(mn) - abs(a[i] - a[j]));
      }
    }
    cout << ans << "\n";
  }
  void solve2() {
    ll ans = -lnf;
    for (int mask = 0; mask < (1 << n); ++mask) {
      if (__builtin_popcount(mask) < 2) {
        continue;
      }
      vt<ll> g;
      ll sum = 0;
      for (int i = 0; i < n; ++i) {
        if (mask >> i & 1) {
          g.push_back(a[i]);
          sum += b[i];
        }
      }
      sort(g.begin(), g.end());
      ans = max(ans, sum - g.back() + g[0]);
    }
    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] >> b[i];
  }
  if (subtask() == 3) {
    sub3::solve2();
  }

  return 0;
}

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