제출 #1125768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125768		duckindog	메기 농장 (IOI22_fish)	C++20	0 / 100	37 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 w[SZ][SZ], 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) w[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] + w[i][j];
    }
    
    for (int j = 1; j <= m; ++j) { 
      { // calculate inc
        if (j > 1) { // start of inc
          { // best[<i][j] -> inc[i][j] or inc[i][j - 1] -> inc[i][j]
            long long small = 0, ma = 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]);
              ma = max(ma, inc[i][j - 1] - h[i][j - 1] - h[i][j]);
              ret = max(ret, small + h[i][j + 1] + h[i][j - 1]);  
              ret = max(ret, ma + h[i][j - 1] + h[i][j + 1]);
            }
          }

          { // best[>i][j] -> inc[i][j]
            long long ma = 0;
            for (int i = m; i >= 1; --i) { 
              auto& ret = inc[i][j];
              ma = max(ma, best[i][j - 2]);
              ret = max(ret, ma + 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 f
        for (int i = 0; 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: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16