oj.uz

Submission #1080957

# Submission time Handle Problem Language Result Execution time Memory
1080957 2024-08-29T16:16:52 Z allin27x Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 4912 KB 
#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],  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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 4912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 1036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 1036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 4912 KB Time limit exceeded
2 Halted 0 ms 0 KB -