Submission #1216151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216151		Mousa_Aboubaker	Catfish Farm (IOI22_fish)	C++20	0 / 100	27 ms	11460 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<int> cc;
  if (x[ord[0]] != 0)
    cc.push_back(0);
  if (x[ord[m - 1]] != n - 1)
    cc.push_back(n - 1);
  for (int i = 0; i < m; i++)
    cc.push_back(x[ord[i]]);
  for (int i = 1; i < m; i++)
    if (x[ord[i]] - x[ord[i - 1]] != 1)
      cc.push_back(x[ord[i - 1]] + 1);
  sort(cc.begin(), cc.end());
  cc.erase(unique(cc.begin(), cc.end()), cc.end());
  for (auto &i : x)
    i = lower_bound(cc.begin(), cc.end(), i) - cc.begin();
  int k = cc.size();
  vector<int> v(k);
  for (int i = 0; i < m; i++)
    v[x[ord[i]]] = w[i];
  vector dp(k, vector<ll>(2, -1));
  auto rec = [&](auto self, int i, int j) -> ll
  {
    if(i == k)
      return 0;
    auto &ret = dp[i][j];
    if(~ret)
      return ret;
    ret = self(self, i + 1, 0) + (j == 1 ? v[i] : 0);
    ret = max(ret, self(self, i + 1, 1));
    if(i + 1 < k)
      ret = max(ret, self(self, i + 2, 1) + (j == 0 ? v[i] : 0));
    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