Submission #1125772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125772		duckindog	Catfish Farm (IOI22_fish)	C++20	35 / 100	1108 ms	278736 KiB

fish

#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#include "fish.h"
#endif

const int N = 300'000 + 10;
int n, m;
struct Fish { 
  int x, y, w;
} fish[N];

namespace sub6 { 
  const int SZ = 3000 + 10;
  long long h[SZ][SZ];
  long long inc[SZ][SZ], dec[SZ][SZ], best[SZ][SZ];

  bool checkCondition() { return m <= 3000; }
  long long solve() {
    for (int i = 1; i <= n; ++i) h[fish[i].x][fish[i].y] = fish[i].w;
    for (int i = 1; i <= m; ++i) { 
      for (int j = 1; j <= m; ++j) h[i][j] += h[i - 1][j];
    }

    for (int j = 1; j <= m; ++j) { 
      { // calculate inc
        if (j > 1) { // start of inc
          { // best[<i][j] -> best i j
            long long small = 0;
            for (int i = 1; i <= m; ++i) { 
              auto& ret = inc[i][j];
              small = max(small, best[i - 1][j - 2] - h[i - 1][j - 1]);
              ret = max(ret, small + h[i][j + 1] + h[i][j - 1]);  
            }
          }

          { // best[>i][j] -> best i j
            long long great = 0;
            for (int i = m; i >= 1; --i) { 
              auto& ret = inc[i][j];
              great = max(great, best[i][j - 2]);
              ret = max(ret, great + h[i][j + 1]);
            }
          }
        }

        { // pre is inc and now is inc
          long long ma = 0;
          for (int i = 1; i <= m; ++i) { 
            auto& ret = inc[i][j];
            ma = max(ma, inc[i][j - 1] - h[i][j - 1] - h[i][j]);
            ret = max(ret, ma + h[i][j - 1] + h[i][j + 1]);
          }
        }
      }

      { // calculate dec
        long long ma = 0;
        for (int i = m; i >= 1; --i) { 
          auto& ret = dec[i][j];
          ma = max(ma, dec[i][j - 1]);
          ret = max({ret, ma - h[i][j] + h[i][j + 1], inc[i][j]});
        }
      }

      { // calculate best
        for (int i = 1; i <= m; ++i) {
          best[i][j] = max({best[i][j], inc[i][j], dec[i][j]});
          best[0][j] = max(best[0][j], best[i][j - 1]);
        }
      }
    }
    
    long long answer = 0;
    for (int i = 0; i <= m; ++i) answer = max(answer, best[i][m]);
    return answer;
  }
}

long long max_weights(int inN, int inM, 
                        vector<int> inX, vector<int> inY, vector<int> inW) {
  { // input
    n = inM; m = inN;
    for (int i = 1; i <= n; ++i) 
      fish[i] = {inY[i - 1] + 1, inX[i - 1] + 1, inW[i - 1]};
  }

  if (sub6::checkCondition()) return sub6::solve();
  
  return 0;
}

#ifdef LOCAL
int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> X(M), Y(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
  }

  long long result = max_weights(N, M, X, Y, W);
  printf("%lld\n", result);
  return 0;
}
#endif

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