Submission #1181196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181196		madamadam3	Catfish Farm (IOI22_fish)	C++20	0 / 100	975 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]));

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

  /*
    DP solution: 
    observe that the best length in column i only depends on the length of the pier at column i - 1
    (it alters which adjacent fish can be used)
    how to make use of this? define DP[i][l] to be best value when we processed the first i rows and length of pier[i] = l
    DP[i][l] = max(DP[i - 1][length of prev] for all possible previous lengths)

    this solution runs on O(n^3) time + O(m) preprocessing
    but what about when there is an empty col, high value col, then empty col adjacent? this solution would make the middle row empty, and max length piers on the others
    so we would double count values in that case. solution? force the lengths to either increase then decrease or decrease then increase, monotonically
    DP[i][l][increasing][first] = best length processed indices to i, if length of i is l, and we're increasing, and we're the first element to be increasing
  */

 ll DP[N+1][N+1][2][2];
 for (int i = 0; i <= N; i++) {
  for (int j = 0; j <= N; j++) {
    DP[j][i][0][0] = DP[j][i][0][1] = DP[j][i][1][0] = DP[j][i][1][1] = 0LL;
  }
 }

 ll ans = 0;

 for (int i = 1; i <= N; i++) {
  for (int ex = 0; ex <= N; ex++) {
    for (int oex = 0; oex <= N; oex++) {
      for (int increasing = 0; increasing <= 1; increasing++) {
        if (increasing == 1 && oex > ex && oex != 0) continue;
        else if (increasing == 0 && ex > oex) continue;

        ll leftContrib = prefix[i - 1][ex] - prefix[i - 1][min(oex, ex)];
        ll rightContrib = prefix[i+1][ex];
        ll ourRemoved = prefix[i][min(oex, ex)];

        DP[i][ex][increasing][0] = max(DP[i][ex][increasing][0], DP[i-1][oex][increasing][0] + leftContrib + rightContrib - ourRemoved);
        DP[i][ex][increasing][1] = max(DP[i][ex][increasing][1], DP[i-1][oex][1-increasing][0] + leftContrib + rightContrib - ourRemoved);

        ans = max({ans, DP[i][ex][increasing][0], DP[i][ex][increasing][1]});
      }
    }
  }
 }

 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