Submission #1125744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125744		zNatsumi	Catfish Farm (IOI22_fish)	C++20	38 / 100	1096 ms	15752 KiB

fish

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5,
          M = 3e5 + 5;

int n, m;
struct info{
  int x, y, w;
  info(){}
  info(int x, int y, int w): x(x), y(y), w(w) {}
} fish[M];

namespace sub1{
  long long solve(){
    long long res = 0LL;
    for(int i = 1; i <= m; i++) res += fish[i].w;
    return res;
  }
}

namespace sub5{
  long long dp[3005][3005][2], weight[3005][3005];

  long long solve(){
    for(int i = 1; i <= m; i++) weight[fish[i].x][fish[i].y] = fish[i].w;

    long long res = 0;
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= n; j++)
        for(int z = 0; z <= 1; z++) dp[i][j][z] = max(dp[i][j][z], dp[i - 1][j][z]);
      if(i > 1){ // case 0
        long long add = 0, sub = 0;
        for(int j = 1; j <= n; j++){
          add += weight[i][j];
          sub += weight[i - 1][j];
          for(int z = j; z <= n; z++) dp[i][j][0] = max(dp[i][j][0], dp[i - 1][z][0] + add - sub);
        }
        for(int j = 1; j <= n; j++) dp[i][n][0] = max({dp[i][n][0], dp[i - 2][j][0] + add, dp[i - 2][j][1] + add});
        for(int j = 1; j <= n; j++) res = max(res, dp[i][j][0]);
      }
      if(i < n){
        long long add = 0;
        for(int j = 1; j <= n; j++){
          add += weight[i][j];
          long long sub = 0;
          for(int z = 1; z <= j; z++){
            sub += weight[i][z];
            dp[i][j][1] = max(dp[i][j][1], dp[i - 1][z][1] + add - sub);
          }
        }
        add = 0;
        for(int j = 1; j <= n; j++){
          add += weight[i][j];
          for(int z = 1; z <= n; z++) dp[i][j][1] = max({dp[i][j][1], dp[i - 1][z][0] + add, dp[i - 2][z][1]});
        }
        res = max(res, dp[i][n][1]);
      }
    }
    return res;
  }
}

int64_t max_weights(int _N, int _M, vector<int> _X, vector<int> _Y, vector<int> _W){
  n = _N; m = _M;
  for(int i = 0; i < m; i++) fish[i + 1] = info(_X[i] + 1, _Y[i] + 1, _W[i]);

  bool flag1 = true;
  for(int i = 1; i <= m; i++) if(!(fish[i].x & 1)){ flag1 = false; break; }

  if(flag1) return sub1::solve();
  else return sub5::solve();
}

//#define zNatsumi
#ifdef zNatsumi

int main(){
  cin.tie(0)->sync_with_stdio(0);
  #define task "test"
  if(fopen(task ".inp", "r")){
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  int n, m; cin >> n >> m;
  vector<int> x(m), y(m), w(m);
  for(int i = 0; i < m; i++) cin >> x[i] >> y[i] >> w[i];

  cout << max_weights(n, m, x, y, w);
}

#endif

• Subtask 1: 3 / 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