Submission #684934

#	Time	Username	Problem	Language	Result	Execution time	Memory
684934		Konti2	Catfish Farm (IOI22_fish)	C++17	52 / 100	1096 ms	294708 KiB

fish

#include <bits/stdc++.h>
#include "fish.h"

using namespace std;

using ll = long long;

ll t[3001][3001];
ll dp[3001][3001][2];
ll sum[3001][3001];

ll max_weights(int N, int M, vector<int> x, vector<int> y, vector<int> w){
	  ll ans = 0;
	  ll pop;
	  for (int i = 0; i < M; i++){
		  t[x[i]][y[i]] = w[i];
	  }
	  for (int i = 0; i < N; i++){
		  for (int h = 1; h <= N; h++){
			  sum[i][h] = t[i][h-1] + sum[i][h-1];
		  }
		  if (i){
			  // CASE 1 a >= b
			  dp[i][0][1] = dp[i-1][0][1];
			  ans = max(ans, dp[i][0][1]);
			  for (int a = 1; a <= N; a++){
				  dp[i][a][1] = max(dp[i-1][a][1], dp[i][a-1][1] + t[i-1][a-1]);
				  ans = max(ans, dp[i][a][1]);
			  }
			  // CASE 2 b >= a;
			  dp[i][N][0] = max(dp[i-1][N][0], dp[i-1][N][1]);
			  ans = max(ans, dp[i][N][0]);
			  for (int a = N-1; a >= 0; a--){
				  dp[i][a][0] = max(dp[i][a+1][0] + t[i][a], max(dp[i-1][a][0], dp[i-1][a][1]));
				   ans = max(ans, dp[i][a][0]);
			  }
			  if (i-1){
				// CASE 3 min(a,b,c) == b == 0 && a >= c
				dp[i][0][1] = max(dp[i][0][1], max(dp[i-2][0][1], dp[i-2][0][0]));
				ans = max(ans, dp[i][0][1]);
				for (int a = 1; a <= N; a++){
					dp[i][a][1] = max(dp[i][a][1], max(dp[i][a-1][1] + t[i-1][a-1], max(dp[i-2][a][0], dp[i-2][a][1]) + sum[i-1][a]));
					 ans = max(ans, dp[i][a][1]);
				}
				// CASE 4 min(a,b,c) == b == 0 && c >= a;
				dp[i][N][1] = max(dp[i][N][1], max(dp[i-2][N][1], dp[i-2][N][0]) + sum[i-1][N]);
				pop = max(dp[i-2][N][1], dp[i-2][N][0]) + sum[i-1][N];
				ans = max(ans, dp[i][N][1]);
				for (int a = N-1; a >= 0; a--){
					dp[i][a][1] = max(dp[i][a][1], max(pop, max(dp[i-2][a][0], dp[i-2][a][1]) + sum[i-1][a]));
					 pop = max(pop, max(dp[i-2][a][0], dp[i-2][a][1]) + sum[i-1][a]);
					 ans = max(ans, dp[i][a][1]);
				}
			}
		}
	}
			  
			  
						  
	  
	  return ans;
  }
	
/*
	
int main(){
	int n;
	cin >> n;
	int m;
	cin >> m;
	vector<int> x(m);
	vector<int> y(m);
	vector<int> w(m);
	for (int i = 0; i < m; i++){
		cin >> x[i];
		cin >> y[i];
		cin >> w[i];
	}
	cout << max_weights(n, m, x, y, w);
	return 0;
}

*/		  

• 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