Submission #1180676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180676		madamadam3	Catfish Farm (IOI22_fish)	C++20	0 / 100	972 ms	2162688 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
using vi = vector<int>;
using vl = vector<ll>;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define pb push_back

/*
  Time log:
  - first start: 1048am
  - 3/100: 1100am
  - first stop: 1128am
  - second start: 337pm
  - 416pm finally stopped being stupid and got 9/100 (+6 points)
  - second end:
  - overall time used: 
*/

/*
  NxN grid of cells
  grid[c][r] = the cell at column c row r
  grid[0][r] is the westernmost point, and grid[N-1][r] is the easternmost point
  grid[c][0] = southernmost point, grid[c][N-1] northermost point

  M catfishes
  X[i], Y[i] for i < M are column and row of fish i
  W[i] = weight of fish i
  a catfish can be caught if grid[ci][ri] is empty and grid[ci-1][ri] or grid[ci+1][ri] has a pier tile
  a pier extends from grid[cP][0] to grid[cP][rP]
*/

int N, M;
vi X, Y; vector<ll> W;

bool cmp(int a, int b) { // compare two fish in the same col
  return X[a] == X[b] ? Y[a] < Y[b] : X[a] < X[b];
}

void output_grid(vector<vl> &grid) {
  for (int i = 0; i < sz(grid); i++) {
    for (int j = 0; j < sz(grid[i]); j++) {
      cout << grid[i][j] << " ";
    }
    cout << "\n";
  }
}

// I think if i stop being stupid about implementation a simple DP will get 70/100
ll max_weights(int _N, int _M, vi _X, vi _Y, vi _W) {
  N = _N; M = _M; X = _X; Y = _Y; for (int i = 0; i < M; i++) W.pb(ll(_W[i]));

  vl fish(M); iota(all(fish), 0);
  sort(all(fish), cmp);
  int maxy = 2 + (int) *max_element(all(Y));

  vector<vl> grid(N+2, vl(maxy, 0LL));
  for (int i = 0; i < M; i++) grid[X[fish[i]]+1][Y[fish[i]]+1] = W[fish[i]];
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= maxy; j++) {
      grid[i][j] = grid[i][j - 1] + grid[i][j];
    }
  }

  // int prev[N+1][maxy];
  vector<vl> DP(N+1, vl(maxy, 0LL)); // DP[i][j] = best score if we extend pier at position i by j places
  ll ans = 0;
  for (int i = 1; i <= N; i++) {
    for (int nex = 0; nex <= maxy; nex++) {
      DP[i][nex] = 0;
      // int bestOex = 0;
      for (int oex = 0; oex <= maxy; oex++) {
        ll prevContrib = DP[i - 1][oex] - grid[i][min(oex, nex)]; // answer from before, but we have to remove what we newly cover
        ll ourContrib = grid[i-1][nex] - grid[i-1][min(oex, nex)]; // new adjacent except whats covered by oex
        if (i == N - 1) ourContrib += grid[i+1][nex];
        ll here = prevContrib + ourContrib;

        if (here > DP[i][nex]) {
          DP[i][nex] = here;
          // bestOex = i;
        }
      }

      // prev[i][nex] = bestOex;
      ans = max(ans, DP[i][nex]);
    }
  }

  // int bfirst = 0; for (int i = 0; i <= N; i++) {if (DP[N][i] > DP[N][bfirst]) bfirst = i;}
  // vi hist;
  // int cur = N, ex = bfirst;
  // while (cur > 0) {
  //   hist.push_back(ex);
  //   ex = prev[cur][ex];
  //   cur --;
  // }

  // output_grid(grid);
  // cout << "\n\n";
  // output_grid(DP);
  // cout << "\n";

  // reverse(all(hist));
  // for (int i = 0; i < N; i++) {
  //   cout << "Extend " << i << " by " << hist[i] << "\n";
  // }

  return ans;
}

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