Submission #627037

#	Time	Username	Problem	Language	Result	Execution time	Memory
627037		lunchbox	Catfish Farm (IOI22_fish)	C++17	100 / 100	502 ms	49020 KiB

fish

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

typedef long long ll;
typedef vector<int> vi;

const ll INF = 1e18;

ll max_weights(int n, int m, vi x, vi y, vi w) {
  vector<vector<pair<int, ll>>> s(n + 1);
  for (int i = 0; i < m; i++)
    s[x[i] + 1].push_back({y[i] + 1, w[i]});
  for (int i = 0; i <= n; i++) {
    s[i].push_back({0, 0});
    s[i].push_back({n + 1, 0});
    sort(s[i].begin(), s[i].end());
    ll x = 0;
    for (auto &[j, w] : s[i]) {
      x += w;
      w = x;
    }
  }
  vector<vi> p(n + 1);
  auto pos = [&](int i, int k) {
    return lower_bound(p[i].begin(), p[i].end(), k) - p[i].begin();
  };
  auto sum = [&](int i, int k) {
    return s[i][upper_bound(s[i].begin(), s[i].end(), make_pair(k, (ll) 0)) - s[i].begin() - 1].second;
  };
  vector<vector<array<ll, 2>>> f(n + 1);
  p[0].push_back(0);
  f[0].assign(1, {-INF, -INF});
  f[0][0][0] = f[0][0][1] = 0;
  for (int i = 1; i <= n; i++) {
    for (auto [j, w] : s[i - 1])
      p[i].push_back(j);
    for (auto [j, w] : s[i])
      p[i].push_back(j);
    sort(p[i].begin(), p[i].end());
    p[i].erase(unique(p[i].begin(), p[i].end()), p[i].end());
    int m = p[i].size();
    f[i].assign(m + 1, {-INF, -INF});
    vector<ll> a(m + 1, -INF), b(m + 1, -INF), c(m + 1, -INF), d(m + 1, -INF);
    for (int k = 0; k < (int) p[i - 1].size(); k++) {
      a[pos(i, p[i - 1][k])] = max(f[i - 1][k][0], f[i - 1][k][1]) + sum(i, p[i - 1][k]);
      d[pos(i, p[i - 1][k])] = f[i - 1][k][1] - sum(i - 1, p[i - 1][k]);
    }
    if (i > 1)
      for (int k = 0; k < (int) p[i - 2].size(); k++) {
        b[pos(i, p[i - 2][k])] = max(f[i - 2][k][0], f[i - 2][k][1]);
        c[pos(i, p[i - 2][k])] = max(f[i - 2][k][0], f[i - 2][k][1]) + sum(i - 1, p[i - 2][k]);
      }
    for (int k = m - 1; k >= 0; k--) {
      a[k] = max(a[k], a[k + 1]);
      c[k] = max(c[k], c[k + 1]);
    }
    for (int k = 0; k < m; k++) {
      b[k + 1] = max(b[k + 1], b[k]);
      d[k + 1] = max(d[k + 1], d[k]);
    }
    for (int k = 0; k <= m; k++) {
      f[i][k][0] = max(f[i][k][0], a[k] - sum(i, p[i][k]));
      f[i][k][1] = max(f[i][k][1], d[k] + sum(i - 1, p[i][k]));
      if (i > 1) {
        f[i][k][1] = max(f[i][k][1], b[k] + sum(i - 1, p[i][k]));
        f[i][k][1] = max(f[i][k][1], c[k]);
      }
      f[i][k][0] = max(f[i][k][0], f[i][k][1]);
    }
  }
  ll ans = 0;
  for (auto v : f[n]) {
    ans = max(ans, v[0]);
    ans = max(ans, v[1]);
  }
  return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16