Submission #707362

#	Time	Username	Problem	Language	Result	Execution time	Memory
707362		Johann	Catfish Farm (IOI22_fish)	C++17	52 / 100	1144 ms	2097152 KiB

fish

#include "fish.h"

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

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

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

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W)
{
  vvi grid(N + 4, vi(N, 0)); // becomes prefix grid

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

  for (int x = 0; x < sz(grid); ++x)
    for (int y = 1; y < sz(grid[0]); ++y)
      grid[x][y] += grid[x][y - 1];

  vvi dpg(sz(grid), vi(sz(grid[0]), 0)); // growth stack thing
  vvi dp(sz(grid), vi(sz(grid[0]), 0));  // normal all dp
  vi dpm(sz(grid), 0);                   // maximum einer Spaltes
  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
    for (int y = 0; y < sz(grid[0]); ++y)
    {
      // Case 1 - last tower in x-1 and smaller y
      c1 = max(c1, dpg[x - 1][y] - grid[x - 1][y] - grid[x][y]);
      dpg[x][y] = max(dpg[x][y], grid[x - 1][y] + grid[x + 1][y] + c1);

      // Case 2 - last tower in x-2 and smaller y
      c2 = max(c2, dp[x - 2][y] - grid[x - 1][y]);
      dpg[x][y] = max(dpg[x][y], grid[x - 1][y] + grid[x + 1][y] + 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] - grid[x][y] + grid[x + 1][y]);

      // 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] + grid[x + 1][y]);

      // Case 5 - Last Tower in x-3
      dpg[x][y] = max(dpg[x][y], dpm[x - 3] + grid[x - 1][y] + grid[x + 1][y]);
      // keep track for dpg & dpm
      dp[x][y] = max(dp[x][y], dpg[x][y]);
      dpm[x] = max(dpm[x], dp[x][y]);
    }
  }

  return *max_element(all(dpm));
}

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