Submission #703200

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
703200	2023-02-26T14:23:24 Z	n1k	Catfish Farm (IOI22_fish)	C++17	52 / 100	867 ms	2097152 KB

fish

#include <bits/stdc++.h>

#define ll long long
#define vt vector
#define pb push_back
#define ar array
#define all(x) (x).begin(), (x).end()
#define sz(x) (x).size()

using namespace std;

/*
 ## TAKE IT EASY ##
 1. simplify
 2. add new elements
 3. brute force solution
 4. optimize
 5. start implementing
*/

// --- templates ---

// --- code ---

const int N = 3000 + 10, FLOW = 3;

ll dp[N][FLOW][N];

ll max_weights(int n, int m, vt<int> X, vt<int> Y, vt<int> W){
	memset(dp, 0, sizeof dp);

	int h = n + 5;

	vt<vt<ll>> a(n + 5, vt<ll>(h));

	for(int i = 0; i < m; i++){
		a[X[i]][Y[i] + 1] = W[i];
	}

	for(int i = 0; i < n; i++){
		for(int j = 1; j < h; j++){
			a[i][j] += a[i][j - 1];
		}
	}

	for(int i = 0; i < n; i++){
		for(int flow = 0; flow < FLOW; flow++){
			vt<ll> sufmax(h + 5), prefmax(h + 5);
			if(i){
				for(int h1 = h; h1 >= 0; h1--){
					sufmax[h1] = max(sufmax[h1 + 1], dp[i - 1][flow][h1]);
				}
				prefmax[0] = dp[i - 1][flow][0];
				for(int h1 = 1; h1 < h; h1++){
					prefmax[h1] = max(prefmax[h1 - 1], dp[i - 1][flow][h1] - a[i - 1][h1] - (flow == 2 ? 0 : a[i][h1]));
				}
			}

			for(int h2 = 0; h2 < h; h2++){
				if(i == 0){
					dp[i][1][h2] = max(dp[i][1][h2], a[i + 1][h2]);
				}else{
					if(flow == 0){
						// h1 > h2
						dp[i][0][h2] = max(dp[i][0][h2], sufmax[h2 + 1] + a[i + 1][h2] - a[i][h2]);
						// h1 == h2
						dp[i][1][h2] = max(dp[i][1][h2], dp[i - 1][flow][h2] + a[i + 1][h2] - a[i][h2]);
					}else if(flow == 1){
						// h1 > h2
						dp[i][0][h2] = max(dp[i][0][h2], sufmax[h2 + 1] + a[i + 1][h2] - a[i][h2]);
						// h1 <= h2
						dp[i][1][h2] = max(dp[i][1][h2], prefmax[h2] + a[i + 1][h2] + a[i - 1][h2]);
					}else{
						// h1 > h2
						dp[i][1][h2] = max(dp[i][1][h2], sufmax[h2 + 1] + a[i + 1][h2]);
						// h1 <= h2
						dp[i][1][h2] = max(dp[i][1][h2], prefmax[h2] + a[i + 1][h2] + a[i - 1][h2]);
					}
				}
				if(i)
					dp[i][2][h2] = max(dp[i - 1][0][h2], dp[i - 1][1][h2]);
			}
		}
	}

	ll ans = 0;

	for(int flow = 0; flow < FLOW; flow++){
		for(int h1 = 0; h1 < h; h1++){
			ans = max(ans, dp[n - 1][flow][h1]);
		}
	}

	return ans;
}

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	801 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	213004 KB	Output is correct
2	Runtime error	862 ms	2097152 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	867 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	213036 KB	Output is correct
2	Correct	96 ms	213004 KB	Output is correct
3	Correct	96 ms	213024 KB	Output is correct
4	Correct	89 ms	212940 KB	Output is correct
5	Correct	84 ms	213040 KB	Output is correct
6	Correct	78 ms	213020 KB	Output is correct
7	Correct	96 ms	212984 KB	Output is correct
8	Correct	79 ms	212940 KB	Output is correct
9	Correct	80 ms	213224 KB	Output is correct
10	Correct	84 ms	213852 KB	Output is correct
11	Correct	80 ms	213180 KB	Output is correct
12	Correct	84 ms	213700 KB	Output is correct
13	Correct	83 ms	213024 KB	Output is correct
14	Correct	86 ms	213820 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	213036 KB	Output is correct
2	Correct	96 ms	213004 KB	Output is correct
3	Correct	96 ms	213024 KB	Output is correct
4	Correct	89 ms	212940 KB	Output is correct
5	Correct	84 ms	213040 KB	Output is correct
6	Correct	78 ms	213020 KB	Output is correct
7	Correct	96 ms	212984 KB	Output is correct
8	Correct	79 ms	212940 KB	Output is correct
9	Correct	80 ms	213224 KB	Output is correct
10	Correct	84 ms	213852 KB	Output is correct
11	Correct	80 ms	213180 KB	Output is correct
12	Correct	84 ms	213700 KB	Output is correct
13	Correct	83 ms	213024 KB	Output is correct
14	Correct	86 ms	213820 KB	Output is correct
15	Correct	97 ms	213744 KB	Output is correct
16	Correct	89 ms	213116 KB	Output is correct
17	Correct	100 ms	215608 KB	Output is correct
18	Correct	102 ms	215564 KB	Output is correct
19	Correct	93 ms	215500 KB	Output is correct
20	Correct	95 ms	215500 KB	Output is correct
21	Correct	107 ms	215580 KB	Output is correct
22	Correct	108 ms	217420 KB	Output is correct
23	Correct	101 ms	214152 KB	Output is correct
24	Correct	110 ms	214928 KB	Output is correct
25	Correct	87 ms	213736 KB	Output is correct
26	Correct	89 ms	214108 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	213036 KB	Output is correct
2	Correct	96 ms	213004 KB	Output is correct
3	Correct	96 ms	213024 KB	Output is correct
4	Correct	89 ms	212940 KB	Output is correct
5	Correct	84 ms	213040 KB	Output is correct
6	Correct	78 ms	213020 KB	Output is correct
7	Correct	96 ms	212984 KB	Output is correct
8	Correct	79 ms	212940 KB	Output is correct
9	Correct	80 ms	213224 KB	Output is correct
10	Correct	84 ms	213852 KB	Output is correct
11	Correct	80 ms	213180 KB	Output is correct
12	Correct	84 ms	213700 KB	Output is correct
13	Correct	83 ms	213024 KB	Output is correct
14	Correct	86 ms	213820 KB	Output is correct
15	Correct	97 ms	213744 KB	Output is correct
16	Correct	89 ms	213116 KB	Output is correct
17	Correct	100 ms	215608 KB	Output is correct
18	Correct	102 ms	215564 KB	Output is correct
19	Correct	93 ms	215500 KB	Output is correct
20	Correct	95 ms	215500 KB	Output is correct
21	Correct	107 ms	215580 KB	Output is correct
22	Correct	108 ms	217420 KB	Output is correct
23	Correct	101 ms	214152 KB	Output is correct
24	Correct	110 ms	214928 KB	Output is correct
25	Correct	87 ms	213736 KB	Output is correct
26	Correct	89 ms	214108 KB	Output is correct
27	Correct	335 ms	283876 KB	Output is correct
28	Correct	167 ms	226308 KB	Output is correct
29	Correct	415 ms	296544 KB	Output is correct
30	Correct	447 ms	296524 KB	Output is correct
31	Correct	430 ms	296552 KB	Output is correct
32	Correct	175 ms	227660 KB	Output is correct
33	Correct	408 ms	296568 KB	Output is correct
34	Correct	426 ms	296552 KB	Output is correct
35	Correct	389 ms	288640 KB	Output is correct
36	Correct	420 ms	296424 KB	Output is correct

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	867 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	801 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Submission #703200

Compilation message