제출 #1216177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216177		Mousa_Aboubaker	메기 농장 (IOI22_fish)	C++20	0 / 100	949 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];
  int m2 = min(n + 1, *max_element(y.begin(), y.end()) + 2);
  vector dp(n, vector(m2, vector<ll>(m2, -1)));
  // dp[i][j] = i is the current cell, j is the current height
  auto rec = [&](auto self, int i, int j, int k) -> ll
  {
    if (i == n)
      return 0;
    auto &ret = dp[i][j][k];
    if (~ret)
      return ret;
    ret = 0;
    if(i == n-1)
    {
      return max(0ll, (j ? pref[j - 1][i] : 0) - (k ? pref[k - 1][i] : 0));
    }
    for(int l = 0; l < m2; l++)
      ret = max(ret, self(self, i + 1, k, l) + max(0ll, (max(j, l) ? pref[max(j, l) - 1][i] : 0) - (k ? pref[k - 1][i] : 0)));
    return ret;
  };
  for(int i = 0; i < m2; i++)
    rec(rec, 0, 0, i);
  ll mx = 0;
  for(auto i: dp)
    for(auto j: i)
      for(auto k: j)
        mx = max(mx, k);
  return mx;
}

• 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