Submission #1223341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223341		brinton	Catfish Farm (IOI22_fish)	C++20	0 / 100	1002 ms	2162688 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W) {
  vector<vector<long long>> fish(N,vector<long long>(N,0));
  for(int i = 0;i < M;i++){
    fish[X[i]][Y[i]] = W[i];
  }
  

  vector<vector<long long>> pref = fish;
  for(int x = 0;x < N;x++){
    for(int y = 1;y < N;y++) pref[x][y] += pref[x][y-1];
  }
  auto sum = [&](int x,int l,int r){
    if(x >= N || x < 0) return 0LL;
    if(l == 0) return pref[x][r];
    if(l > r) return 0LL;
    return pref[x][r]-pref[x][l-1];
  };

  vector dpinc(N,vector(N,0LL));
  vector dpdec(N,vector(N,0LL));
  auto vmax = [&](vector<long long>& v){
    return *max_element(v.begin(),v.end());
  };
  for(int cx = 1;cx < N;cx++){
    // dp inc
    for(int py = 0;py < N;py++){
      for(int cy = py;cy < N;cy++){
        dpinc[cx][cy] = max(dpinc[cx][cy],dpinc[cx-1][py]+sum(cx-1,py+1,cy));
      }
    }
    // dp dec
    for(int py = 0;py < N;py++){
      for(int cy = 0;cy <= py;cy++){
        dpdec[cx][cy] = max(dpdec[cx][cy],dpdec[cx-1][py]+sum(cx,cy+1,py));
        dpdec[cx][cy] = max(dpdec[cx][cy],dpinc[cx-1][py]+sum(cx,cy+1,py));
      }
    }

    if(cx == 1){
      for(int cy = 0;cy < N;cy++){
        long long prevV = sum(cx-1,0,cy);
        dpinc[cx][cy] = max(dpinc[cx][cy],prevV);
        dpdec[cx][cy] = max(dpdec[cx][cy],prevV);
      }
      continue;
    }
    // skip one
    for(int py = 0;py < N;py++){
      for(int cy = 0;cy < N;cy++){
        long long prevV = max(dpinc[cx-2][py],dpdec[cx-2][py])+sum(cx-1,0,max(py,cy));
        dpinc[cx][cy] = max(dpinc[cx][cy],prevV);
        dpdec[cx][cy] = max(dpdec[cx][cy],prevV);
      }
    }
    // skip two
    if(cx == 2) continue;
    long long two_empty = max(vmax(dpinc[cx-3]),vmax(dpdec[cx-3]));
    for(int cy = 0;cy < N;cy++){
      dpinc[cx][cy] = max(dpinc[cx][cy],two_empty);
      dpdec[cx][cy] = max(dpdec[cx][cy],two_empty);
    }
  }

  
  long long ans = max(vmax(dpinc[N-1]),vmax(dpdec[N-1]));
  for(int ly = 0;ly < N;ly++){
    ans = max(ans,dpinc[N-2][ly]+sum(N-1,0,ly));
    ans = max(ans,dpdec[N-2][ly]+sum(N-1,0,ly));
  }
  return ans;
}

• 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