Submission #766274

#	Time	Username	Problem	Language	Result	Execution time	Memory
766274		jakobrs	Catfish Farm (IOI22_fish)	C++17	0 / 100	1146 ms	1394060 KiB

fish

#include "fish.h"

#include <vector>
#include <cstdint>

#include <iostream>

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
  int h = N + 1;
  int64_t sum_up_to[N][h];
  for (int x = 0; x < N; x++) {
    for (int y = 0; y < h; y++) {
      sum_up_to[x][y] = 0;
    }
  }
  for (int i = 0; i < M; i++) {
    sum_up_to[X[i]][Y[i] + 1] = W[i];
  }
  for (int x = 0; x < N; x++) {
    int64_t accum = 0;
    sum_up_to[x][0] = accum;
    for (int y = 1; y < h; y++) {
      accum += sum_up_to[x][y];
      sum_up_to[x][y] = accum;
    }
  }

  int64_t dp[N][h][h];
  for (int i = 0; i < N; i++) {
    for (int x = 0; x < h; x++) {
      for (int y = 0; y < h; y++) {
        dp[i][x][y] = INT64_MIN;
      }
    }
  }

  for (int x = 0; x < h; x++) {
    dp[0][x][0] = 0;
  }

  for (int i = 1; i < N; i++) {
    for (int x = 0; x < h; x++) {
      for (int y = 0; y < h; y++) {
        if (x == y) {
          dp[i][x][y] = 0;
          for (int z = 0; z < h; z++) {
            dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z]);
          }
        } else if (x > y) {
          dp[i][x][y] = 0;
          for (int z = 0; z < h; z++) {
            if (x > y && x > z) {
              dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z] + sum_up_to[i - 1][x] - sum_up_to[i - 1][std::max(y, z)]);
            } else {
              dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z]);
            }
          }
        } else {
          dp[i][x][y] = 0;
          {
            for (int z = 0; z < h; z++) {
              dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z]);
            }
          }
          dp[i][x][y] += sum_up_to[i][y] - sum_up_to[i][x];
        }
      }
    }

    // std::cout << dp[i][0][0] << ' ' << dp[i][0][1] << ' ' << dp[i][1][0] << ' ' << dp[i][1][1] << '\n';
  }

  int64_t best = 0;
  for (int x = 0; x < h; x++) {
    for (int y = 0; y < h; y++) {
      best = std::max(best, dp[N - 1][x][y]);
    }
  }
  
  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