Submission #625753

#	Time	Username	Problem	Language	Result	Execution time	Memory
625753		flashmt	Catfish Farm (IOI22_fish)	C++17	14 / 100	1093 ms	3992 KiB

fish

#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const long long oo = 1LL << 60;

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
  if (n > 3000)
    return 0;

  for (int i = 0; i < m; i++)
    for (int j = i + 1; j < m; j++)
      if (make_pair(x[i], y[i]) > make_pair(x[j], y[j]))
      {
        swap(x[i], x[j]);
        swap(y[i], y[j]);
        swap(w[i], w[j]);
      }


  // f: left, g: right
  vector<long long> f(m, -oo), g(m, -oo);
  long long ans = 0;
  for (int i = 0; i < m;)
  {
    int ii = i + 1;
    while (ii < m && x[ii] == x[i])
      ii++;

    for (int j = i; j < ii; j++)
      if (x[j] < n - 1)
      {
        g[j] = w[j];
        for (int jj = 0; jj < i; jj++)
          if (x[jj] == x[j] - 1 && y[jj] >= y[j]) g[j] = max(g[j], f[jj] + w[j]);
          else g[j] = max(g[j], max(f[jj], g[jj]) + w[j]);

        for (int jj = i; jj < j; jj++)
          g[j] = max(g[j], g[jj] + w[j]);
      }

    for (int j = ii - 1; j >= i; j--)
      if (x[j])
      {
        f[j] = w[j];

        for (int jj = 0; jj < i; jj++)
          if (x[jj] + 1 < x[j]) f[j] = max(f[j], max(f[jj], g[jj]) + w[j]);
          else if (y[jj] > y[j]) f[j] = max(f[j], f[jj] + w[j]);

        for (int jj = j + 1; jj < ii; jj++)
          f[j] = max(f[j], f[jj] + w[j]);
      }

    ans = max({ans, f[i], g[i]});
    i = ii;
  }

  return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 14 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16