Submission #707662

#	Time	Username	Problem	Language	Result	Execution time	Memory
707662		Johann	Catfish Farm (IOI22_fish)	C++17	75 / 100	1087 ms	112520 KiB

fish

#include "fish.h"

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

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef map<ll, ll> mii;
typedef vector<mii> vmii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 3e5 * 1e9 + 100;

void updateIdx(ll y, ll &ny, mii::iterator &itpref0, ll &pref0)
{
  if (itpref0->first == y)
  {
    pref0 = itpref0->second;
    ++itpref0;
  }
  ny = min(itpref0->first, ny);
}

void eraseDuplicates(mii &dp, int N)
{
  ll y = 0, lastY;
  ll lastV = -1;
  while (y < N)
  {
    auto it = dp.lower_bound(y);
    do
    {
      lastV = it->second, lastY = it->first;
      ++it;
      if (it == dp.end())
        return;

    } while (lastV != it->second);
    dp.erase(it);
    y = lastY;
  }
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W)
{
  vmii grid(N + 4); // becomes prefix grid
  for (int x = 0; x < sz(grid); ++x)
    grid[x][0] = 0;

  for (int i = 0; i < M; ++i)
    grid[X[i] + 3][Y[i]] = W[i];

  for (int x = 0; x < sz(grid); ++x)
  {
    ll pref = 0;
    for (auto it = grid[x].begin(); it != grid[x].end(); ++it)
    {
      pref += it->second;
      it->second = pref;
    }
    grid[x][N] = pref;
  }

  vmii dpg(sz(grid));  // growth stack thing
  vmii dp(sz(grid));   // normal all dp
  vi dpm(sz(grid), 0); // maximum einer Spaltes
  for (int i = 0; i < 3; ++i)
    dpg[i][0] = dpg[i][N] = dp[i][0] = dp[i][N] = 0;

  for (int x = 3; x < sz(grid) - 1; ++x) // so i choose the borders
  {
    ll c1 = -INF, c2 = -INF; // running variables for case 1 and 2 // TODO: INIT
    ll y = 0, ny;
    ll pref0 = 0, pref1 = 0, pref2 = 0, dp0 = 0, dpg1 = 0;
    auto itpref0 = grid[x - 1].begin(); // idx for pref x-1
    auto itpref1 = grid[x].begin();     // idx for pref x
    auto itpref2 = grid[x + 1].begin(); // idx for pref x+1
    auto itdp0 = dp[x - 2].begin();     // idx for dp x-2
    auto itdpg1 = dpg[x - 1].begin();   // idx for dpg x-1
    while (y < N)
    {
      // update indices
      ny = INT_MAX;
      updateIdx(y, ny, itpref0, pref0);
      updateIdx(y, ny, itpref1, pref1);
      updateIdx(y, ny, itpref2, pref2);
      updateIdx(y, ny, itdp0, dp0);
      updateIdx(y, ny, itdpg1, dpg1);

      // Case 1 - last tower in x-1 and smaller y
      c1 = max(c1, dpg1 - pref0 - pref1);
      dpg[x][y] = max(dpg[x][y], pref0 + pref2 + c1);

      // Case 2 - last tower in x-2 and smaller y
      c2 = max(c2, dp0 - pref0);
      dpg[x][y] = max(dpg[x][y], pref0 + pref2 + c2);

      // Case 3 - last tower in x-1 and larger y (or if it is smaller, case 1 performs better)
      // here the last tower might be larger than the current one
      dp[x][y] = max(dp[x][y], dpm[x - 1] - pref1 + pref2);

      // Case 4 - Last Tower in x-2 and larger y (or if it is smaller, case 2 performs better)
      dpg[x][y] = max(dpg[x][y], dpm[x - 2] + pref2);

      // Case 5 - Last Tower in x-3
      dpg[x][y] = max(dpg[x][y], dpm[x - 3] + pref0 + pref2);

      // keep track for dpg & dpm
      dp[x][y] = max(dp[x][y], dpg[x][y]);
      dpm[x] = max(dpm[x], dp[x][y]);

      y = ny;
    }
    eraseDuplicates(dp[x], N);
    eraseDuplicates(dpg[x], N);
    dp[x][N] = max(dp[x][N], dp[x].rbegin()->second);
    dpg[x][N] = max(dpg[x][N], dpg[x].rbegin()->second);
  }

  return *max_element(all(dpm));
}

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