Submission #1223263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223263		brinton	Catfish Farm (IOI22_fish)	C++20	0 / 100	969 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+1,vector<long long>(N+1,0));
  for(int i = 0;i < M;i++){
    fish[X[i]+1][Y[i]+1] = W[i];
  }
  vector dp(N+1,vector(N+1,0LL));

  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];
    return pref[x][r]-pref[x][l-1];
  };
  for(int cx = 1;cx <= N;cx++){
    for(int cy = 0;cy <= N;cy++){
      for(int py = 0;py <= N;py++){
        if(cy > py){// cur taller,add back
          dp[cx][cy] = max(dp[cx][cy],dp[cx-1][py]-sum(cx,0,py)+sum(cx+1,0,cy)+sum(cx-1,py+1,cy));
        }else{// 5 3
          dp[cx][cy] = max(dp[cx][cy],dp[cx-1][py]-sum(cx,0,py)+sum(cx+1,0,cy));
        }
        // if(cx == 1 && py == 0 && cy > 2){
        //   cout << dp[cx-1][py] << " -" << sum(cx,0,py) << " +" << sum(cx+1,0,cy) << " +" << sum(cx-1,py+1,cy) << "!" << endl;
        // }
      }
    }
  }

  
  // for(auto &i:dp){
  //   for(auto &j:i) cout << j << " ";cout << endl;
  // }
  // for(auto &i:pref){
  //   for(auto &j:i) cout << j << " ";cout << endl;
  // }
  return *max_element(dp[N].begin(),dp[N].end());
}

• 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