Submission #824809

#	Time	Username	Problem	Language	Result	Execution time	Memory
824809		LittleCube	Catfish Farm (IOI22_fish)	C++17	100 / 100	149 ms	36924 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

// every conponent can only be decreasing and increasing (except for the first and last, they can only be inc/decreasing).
vector<pll> pos[100005];
vector<ll> up[100005], down[100005];
ll non[100005], sz[100005];

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
  for (int i = 0; i < M; i++)
    pos[X[i] + 1].emplace_back(pll(Y[i], W[i]));
  pos[0] = {pll(-1, 0)};
  for (int i = 1; i <= N; i++)
  {
    sz[0] = 1;
    sort(pos[i].begin(), pos[i].end());
    sz[i] = pos[i].size();
  }
  up[0] = {0};
  down[0] = {(ll)-1e18};
  non[0] = -1e18;
  for (int i = 1; i <= N; i++)
  {
    up[i].resize(sz[i]);
    down[i].resize(sz[i]);

    non[i] = max(0LL, non[i - 1]);
    if (!down[i - 1].empty())
      non[i] = max(non[i], down[i - 1].front());
    if (!up[i - 1].empty())
      non[i] = max(non[i], up[i - 1].back());

    {
      ll acc = non[i - 1];
      for (int j = sz[i] - 1, k = sz[i - 1] - 1; j >= 0; j--)
      {
        while (k >= 0 && pos[i - 1][k].F > pos[i][j].F)
          acc = max(acc, down[i - 1][k]), k--;
        down[i][j] = acc + pos[i][j].S;
        acc = max(acc, down[i][j]);
      }
    }
    {
      ll acc = non[i - 1];
      if (!down[i - 1].empty())
        acc = max(acc, down[i - 1].front());
      for (int j = 0, k = 0; j < sz[i]; j++)
      {
        while (k < sz[i - 1] && pos[i - 1][k].F < pos[i][j].F)
          acc = max(acc, up[i - 1][k]), k++;
        up[i][j] = acc + pos[i][j].S;
        acc = max(acc, up[i][j]);
      }
    }
  }
  ll ans = non[N];
  if (!down[N].empty())
    ans = max(ans, down[N].front());
  return ans;
}

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