Submission #1080959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080959		allin27x	Catfish Farm (IOI22_fish)	C++17	0 / 100	1065 ms	54584 KiB

fish

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N= 305;
int dp[N][N][N];
int sfm[N];
int fs[N][9];

long long max_weights(signed n, signed m, std::vector<signed> x, std::vector<signed> y, std::vector<signed> w){
	for (int i=0; i<m; i++) fs[x[i]][y[i]] = w[i];

	for (int h0=0; h0<=n; h0++) {
		for (int h1=0; h1<=n; h1++) {
			if (h0 < h1) {
				for (int r = h0; r<h1; r++) dp[1][h0][h1] += fs[0][r];
			}
			if (h0 > h1) {
				for (int r = h1; r< h0; r++) dp[1][h0][h1] += fs[1][r];
			}
		}
	}

	for (int i=2; i<n; i++) {
		for (int h0=0; h0<=n; h0++) {
			int mx = 0; for (int t=0;  t<=h0; t++) mx = max(mx, dp[i-1][t][h0]);
			sfm[n] = dp[i-1][n][h0]; for (int j=n-1; j>=0; j--) sfm[j] = max(sfm[j+1], dp[i-1][j][h0]);
			int s = 0; for (int h=0; h<h0; h++) s += fs[i][h]; int s1 = 0;
			for (int h=0;  h<=h0; h++) {
				dp[i][h0][h] = max(dp[i][h0][h], s - s1 + sfm[0]); s1 += fs[i][h];
			}
			for (int h = h0 + 1; h <= n; h++) {
				mx = max(mx  + fs[i-1][h-1],  dp[i-1][h][h0]);
				int r = max(mx, sfm[h]);
				dp[i][h0][h] = max(dp[i][h0][h], r);
			}

		}
	}
	// for (int i=0; i<=n; i++) {
	// 	for (int j=0; j<=n; j++) {
	// 		cout<<i<<' '<<j<<' '<<dp[4][i][j]<<'\n';
	// 	}
	// }
	int ans = 0;
	for (int h0=0; h0<=n; h0++) {
		for (int h1=0; h1<=n; h1++) {
			ans = max(ans, dp[n-1][h0][h1]);
		}
	}
	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