Submission #1125753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125753		zNatsumi	Catfish Farm (IOI22_fish)	C++20	3 / 100	76 ms	10824 KiB

fish

#include <bits/stdc++.h>

using namespace std;

const int32_t N = 1e5 + 5,
              M = 3e5 + 5;
const int64_t INF = 1e18;

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 sub6{
  long long dp[3005][3005][2], weight[3005][3005], pref1[3005][3005], pref2[3005][3005], pref3[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 = 0; j <= n + 1; j++){
        for(int z = 0; z <= 1; z++) dp[i][j][z] = max(dp[i][j][z], dp[i - 1][j][z]);
        pref1[i][j] = pref2[i][j] = pref3[i][j] = -INF;
      }

      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];
          dp[i][j][0] = max(dp[i][j][0], pref1[i - 1][j] + 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]);
        for(int j = n; j >= 1; j--) pref1[i][j] = max(pref1[i][j + 1], dp[i][j][0]);
      }

      if(i < n){
        long long add = 0;
        for(int j = 1; j <= n; j++){
          add += weight[i][j];
          dp[i][j][1] = max(dp[i][j][1], pref2[i - 1][j] + add);
        }
        add = 0;
        for(int j = 1; j <= n; j++){
          add += weight[i + 1][j];
          pref2[i][j] = max(pref2[i][j - 1], dp[i][j][1] - add);
          pref3[i][j] = max(pref3[i][j - 1], dp[i][j][1]);
        }

        add = 0;
        for(int j = 1; j <= n; j++){
          add += weight[i][j];
          dp[i][j][1] = max(dp[i][j][1], pref1[i - 1][1] + add);
          if(j >= 2) dp[i][j][1] = max(dp[i][j][1], pref3[i - 2][n]);
        }
        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 sub6::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: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16