Submission #821051

#	Time	Username	Problem	Language	Result	Execution time	Memory
821051		dashka	Catfish Farm (IOI22_fish)	C++17	100 / 100	251 ms	60324 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
  vector<vector<long long>> fishes(N+1);
  vector<vector<int>> states(N+1, {0});
  for (int i = 0; i < M; ++i) {
    ++Y[i];
    for (int j = max(X[i]-1, 0); j <= min(X[i]+1, N-1); ++j) {
      states[j].push_back(Y[i]);
    }
  }
  
  for (int i = 0; i <= N; ++i) {
    sort(states[i].begin(), states[i].end());
    states[i].erase(unique(states[i].begin(), states[i].end()), states[i].end());
    fishes[i].resize(states[i].size());
  }
  for (int i = 0; i < M; ++i) {
    int x = X[i];
    int y = lower_bound(states[x].begin(), states[x].end(), Y[i]) - states[x].begin();
    fishes[x][y] += W[i];
  }
  vector<vector<long long>> dp_up(N+1), dp_down(N+1);
  for (int i = 0; i <= N; ++i) {
    int sz = states[i].size();
    dp_up[i].assign(sz, 0);
    dp_down[i].assign(sz, 0);
    if (i > 1) {
      long long best = max(dp_up[i-2][0], dp_down[i-2][0]), sum = 0;
      for (int j = 0, lef = 0, mid = 0; j < sz; ++j) {
        while (lef+1 < (int)states[i-2].size() && states[i-2][lef+1] <= states[i][j]) {
          ++lef;
          while (mid+1 < (int)states[i-1].size() && states[i-1][mid+1] <= states[i-2][lef]) {
            ++mid;
            best += fishes[i-1][mid];
            sum += fishes[i-1][mid];
          }
          best = max(best, max(dp_up[i-2][lef], dp_down[i-2][lef]) + sum);
        }
        dp_up[i][j] = max(dp_up[i][j], best);
      }
      best = 0;
      sum = accumulate(fishes[i-1].begin(), fishes[i-1].end(), 0LL);
      for (int j = sz-1, lef = states[i-2].size(), mid = states[i-1].size(); j >= 0; --j) {
        while (lef > 0 && states[i-2][lef-1] >= states[i][j]) {
          --lef;
          while (mid > 0 && states[i-1][mid-1] > states[i-2][lef]) {
            --mid;
            sum -= fishes[i-1][mid];
          }
          best = max(best, max(dp_up[i-2][lef], dp_down[i-2][lef]) + sum);
        }
        dp_up[i][j] = max(dp_up[i][j], best);
      }
    }
    if (i > 0) {
      long long best = dp_up[i-1][0], sum = 0;
      for (int j = 0, lef = 0; j < sz; ++j) {
        while (lef+1 < (int)states[i-1].size() && states[i-1][lef+1] <= states[i][j]) {
          ++lef;
          best += fishes[i-1][lef];
          best = max(best, dp_up[i-1][lef]);
        }
        dp_up[i][j] = max(dp_up[i][j], best);
      }
      best = 0;
      sum = accumulate(fishes[i].begin(), fishes[i].end(), 0LL);
      for (int j = sz-1, lef = states[i-1].size(); j >= 0; --j) {
        while (lef > 0 && states[i-1][lef-1] >= states[i][j]) {
          --lef;
          best = max(best, max(dp_down[i-1][lef], dp_up[i-1][lef]) + sum);
        }
        dp_down[i][j] = max(dp_down[i][j], best-sum);
        sum -= fishes[i][j];
      }
    }
  }
  return max(dp_up[N][0], dp_down[N][0]);
}

• 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