Submission #626618

#	Time	Username	Problem	Language	Result	Execution time	Memory
626618		dariasc	Catfish Farm (IOI22_fish)	C++17	0 / 100	977 ms	2097152 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define vec vector
#define ll long long

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {

  ll fish[N][N];
  memset(fish, 0, sizeof fish);
  for (int i = 0; i < M; i++) {
    fish[X[i]][Y[i]] = W[i];
  }

  ll pfx[N][N+1][2];
  memset(pfx, 0, sizeof pfx);
  for (int x = 0; x < N; x++) {
    for (int y = 1; y <= N; y++) {
      ll l = 0;
      if (x > 0) {
        l = fish[x-1][y-1];
      }
      ll r = 0;
      if (x < N-1) {
        r = fish[x+1][y-1];
      }
      pfx[x][y][0] = pfx[x][y-1][0] + l;
      pfx[x][y][1] = pfx[x][y-1][1] + r;
    }
  }

  /*
  for (int x = 0; x <= N; x++) {
    for (int y = 0; y < N; y++) {
      cout << pfx[y][x][0] << ":" << pfx[y][x][1] << " ";
    }
    cout << endl;
  }
  */
  ll dp[N][N+1][3];
  memset(dp, 0, sizeof dp);
  for (int y = 1; y <= N; y++) {
    dp[0][y][0] = pfx[0][y][1];
    dp[0][y][1] = pfx[0][y][1];
    dp[0][y][2] = pfx[0][y][1];
  }
  for (int x = 1; x < N; x++) {
    for (int y = 0; y <= N; y++) {
      dp[x][y][0] = pfx[x][y][0] + pfx[x][y][1];
      dp[x][y][1] = dp[x][y][0];
      dp[x][y][2] = dp[x][y][0];
      for (int k = 0; k <= N; k++) {
        if (x > 2) {
          dp[x][y][0] = max(dp[x][y][0], dp[x-3][k][0] + pfx[x][y][0] + pfx[x][y][1]);
          dp[x][y][0] = max(dp[x][y][0], dp[x-3][k][1] + pfx[x][y][0] + pfx[x][y][1]);
          dp[x][y][0] = max(dp[x][y][0], dp[x-3][k][2] + pfx[x][y][0] + pfx[x][y][1]);
        }
        if (x > 1) {
          ll addend = 0;
          if (y > k) {
            addend = pfx[x][y][0] - pfx[x][k][0];
          }
          dp[x][y][1] = max(dp[x][y][1], dp[x-2][k][0] + addend + pfx[x][y][1]);
          dp[x][y][1] = max(dp[x][y][1], dp[x-2][k][1] + addend + pfx[x][y][1]);
          dp[x][y][1] = max(dp[x][y][1], dp[x-2][k][2] + addend + pfx[x][y][1]);

        }
        if (x > 0) {
          ll addend = 0;
          if (y > k) {
            addend = pfx[x][y][0] - pfx[x][k][0];
          }
          dp[x][y][2] = max(dp[x][y][2], dp[x-1][k][0] - pfx[x-1][min(k,y)][1] + addend + pfx[x][y][1]);
          dp[x][y][2] = max(dp[x][y][2], dp[x-1][k][1] - pfx[x-1][min(k,y)][1] + addend + pfx[x][y][1]);
        }
      }
    }
  }
  /*
  for (int x = 0; x <= N; x++) {
    for (int y = 0; y < N; y++) {
      cout << dp[y][x] << " ";
    }
    cout << endl;
  }*/
  ll best = 0;
  for (int x = 0; x < N; x++) {
    for (int y = 0; y <= N; y++) {
      best = max(dp[x][y][0], best);
      best = max(dp[x][y][1], best);
      best = max(dp[x][y][2], best);
    }
  }

  return best;
}

• 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