Submission #1216162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216162		Mousa_Aboubaker	Catfish Farm (IOI22_fish)	C++20	0 / 100	988 ms	2162688 KiB

fish

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

using ll = long long;

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
  auto n = N, m = M;
  auto x = X, y = Y, w = W;
  if (n == 1)
    return 0;
  // vector<int> ord(m);
  // iota(ord.begin(), ord.end(), 0);
  // sort(ord.begin(), ord.end(), [&](int l, int r)
  //      { return x[l] < x[r]; });
  vector cnt(n, vector<int>(n));
  for (int i = 0; i < m; i++)
  {
    cnt[y[i]][x[i]] = w[i];
  }
  vector pref(n, vector<ll>(n));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      pref[i][j] = cnt[i][j];
  for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j++)
      pref[j][i] += pref[j - 1][i];
  vector dp(n, vector<ll>(n + 1, -1));
  // dp[i][j] = i is the current cell, j is the current height
  auto rec = [&](auto self, int i, int j) -> ll
  {
    if (i == n)
      return 0;
    auto &ret = dp[i][j];
    if (~ret)
      return ret;
    ret = self(self, i + 1, 0) + (j ? pref[j - 1][i] : 0);
    for (int k = 0; k < j - 1; k++)
      ret = max(ret, self(self, i + 1, k + 1) + pref[j - 1][i] - pref[k][i]);
    for (int k = j - 1; k < n; k++)
      ret = max(ret, self(self, i + 1, k + 1));
    if (i + 1 < n)
    {
      for (int k = 1; k <= n; k++)
        ret = max(ret, self(self, i + 2, k) + pref[k - 1][i]);
    }
    return ret;
  };
  return rec(rec, 0, 0);
}

• 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