Submission #1125773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125773		duckindog	Catfish Farm (IOI22_fish)	C++20	0 / 100	36 ms	5956 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];
  inline long long best(int i, int j) { return max(inc[i][j], dec[i][j]); }

  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) { 
              small = max(small, best(i - 1, j - 2) - h[i - 1][j - 1]);
              inc[i][j] = max(inc[i][j], 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) { 
              great = max(great, best(i, j - 2));
              inc[i][j] = max(inc[i][j], great + h[i][j + 1]);
            }
          }
        }

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

            inc[0][j] = max(inc[0][j], inc[i][j - 1]);
          }
        }
      }

      { // calculate dec
        long long ma = 0;
        for (int i = m; i >= 1; --i) { 
          ma = max(ma, dec[i][j - 1]);
          dec[i][j] = max({dec[i][j], ma - h[i][j] + h[i][j + 1], inc[i][j]});
        }
      }
    }
    
    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);
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << '\n';
  return 0;
}
#endif

• 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