Submission #1223364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223364		brinton	Catfish Farm (IOI22_fish)	C++20	52 / 100	997 ms	2162688 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define inf (long long)(1e15)
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
    long long cmax = -inf;
    for(int cy = 0;cy < N;cy++){
      cmax = max(cmax,dpinc[cx-1][cy]-sum(cx-1,0,cy));
      dpinc[cx][cy] = max(dpinc[cx][cy],cmax+sum(cx-1,0,cy));
    }
    // dp dec
    cmax = -inf;
    for(int cy = N-1;cy >= 0;cy--){
      cmax = max(cmax,dpdec[cx-1][cy]+sum(cx,0,cy));
      cmax = max(cmax,dpinc[cx-1][cy]+sum(cx,0,cy));
      dpdec[cx][cy] = max(dpdec[cx][cy],cmax-sum(cx,0,cy));
    }

    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
    cmax = -inf;
    for(int cy = 0;cy < N;cy++){
      cmax = max(cmax,max(dpinc[cx-2][cy],dpdec[cx-2][cy]));
      dpinc[cx][cy] = max(dpinc[cx][cy],cmax+sum(cx-1,0,cy));
      dpdec[cx][cy] = max(dpdec[cx][cy],cmax+sum(cx-1,0,cy));
    }
    cmax = -inf;
    for(int cy = N-1;cy >= 0;cy--){
      cmax = max(cmax,max(dpinc[cx-2][cy],dpdec[cx-2][cy])+sum(cx-1,0,cy));
      dpinc[cx][cy] = max(dpinc[cx][cy],cmax);
      dpdec[cx][cy] = max(dpdec[cx][cy],cmax);
    }
    // skip two(ok)
    if(cx == 2) continue;
    long long two_empty = 0;
    for(int py = 0;py < N;py++){
      two_empty = max(two_empty,dpinc[cx-3][py]+sum(cx-2,0,py));
      two_empty = max(two_empty,dpdec[cx-3][py]+sum(cx-2,0,py));
    }
    // cout << "!" << cx << ":" << two_empty << endl;
    for(int cy = 0;cy < N;cy++){
      dpinc[cx][cy] = max(dpinc[cx][cy],two_empty+sum(cx-1,0,cy));
      dpdec[cx][cy] = max(dpdec[cx][cy],two_empty+sum(cx-1,0,cy));
    }
  }

  
  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));
  }

  // cout << "===== dpinc =====" << endl;
  // for(auto &i:dpinc){
  //   for(auto j:i) cout << j << " ";cout << endl;
  // }
  // cout << "===== dpdec =====" << endl;
  // for(auto &i:dpdec){
  //   for(auto j:i) cout << j << " ";cout << endl;
  // }
  return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16