Submission #627293

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
627293	2022-08-12T11:58:38 Z	JustInCase	Catfish Farm (IOI22_fish)	C++17	44 / 100	134 ms	10852 KB

fish

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <random>
#include <cstdlib>

#define debug(x) std::cout << #x << " " << (x) << '\n';
#define pb push_back
#define mp std::make_pair
#define remax(a, b) a = std::max((a), (b));
#define remin(a, b) a = std::min((a), (b));

#define maxWeights max_weights

int64_t solveSmallN(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
			std::vector<int32_t> w) {
	const int32_t MAX_N = 300;

	std::array<std::array<int64_t, MAX_N>, MAX_N> wPrefSums {};
	std::array<std::array<std::array<int64_t, 3>, MAX_N + 1>, MAX_N + 1> dp {};

	auto getWRangeSum = [&wPrefSums](int32_t startRow, int32_t endRow, int32_t column) -> int64_t {
		if(endRow <= startRow) {
			return 0;
		}

		return wPrefSums[endRow - 1][column] - (startRow == 0 ? 0 : wPrefSums[startRow - 1][column]);
	};

	for(int32_t i = 0; i < m; i++) {
		wPrefSums[y[i]][x[i]] = (int64_t) w[i];
	}

	for(int32_t j = 0; j < n; j++) {
		for(int32_t i = 1; i < n; i++) {
			wPrefSums[i][j] += wPrefSums[i - 1][j];
		}
	}

	for(int32_t j = 1; j < n; j++) {
		for(int32_t lastK = 0; lastK <= n; lastK++) {
			for(int32_t k = 0; k <= n; k++) {
				if(k == 0) {
					remax(dp[j + 1][lastK][2], dp[j][lastK][0] + getWRangeSum(0, lastK, j));
					remax(dp[j + 1][lastK][2], dp[j][lastK][1] + getWRangeSum(0, lastK, j));
				}

				if(lastK <= k) {
					remax(dp[j + 1][k][0], dp[j][lastK][0] + getWRangeSum(lastK, k, j - 1));
					remax(dp[j + 1][k][0], dp[j][lastK][2] + getWRangeSum(lastK, k, j - 1));
				}
				if(lastK >= k) {
					remax(dp[j + 1][k][1], dp[j][lastK][1] + getWRangeSum(k, lastK, j));
					remax(dp[j + 1][k][1], dp[j][lastK][0] + getWRangeSum(k, lastK, j));
					remax(dp[j + 1][k][0], dp[j][lastK][2]);
				}
			}
		}
	}
	
	int64_t ans = 0;
	for(int32_t k = 0; k <= n; k++) {
		remax(ans, dp[n][k][0]);
		remax(ans, dp[n][k][1]);
		remax(ans, dp[n][k][2]);
	}

	return ans;
}

int64_t solveEvenXs(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
			std::vector<int32_t> w) {
	int64_t ans = 0;
	for(int32_t i = 0; i < m; i++) {
		ans += (int64_t) w[i];
	}
	return ans;
}

int64_t solveAllXs0Or1(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
			std::vector<int32_t> w) {
	const int32_t MAX_N = 1e5;

	std::array<std::array<int64_t, 2>, MAX_N> wPrefSums {};

	auto getWRangeSum = [&wPrefSums](int32_t startRow, int32_t endRow, int32_t column) -> int64_t {
		if(endRow <= startRow) {
			return 0;
		}

		return wPrefSums[endRow - 1][column] - (startRow == 0 ? 0 : wPrefSums[startRow - 1][column]);
	};

	for(int32_t i = 0; i < m; i++) {
		wPrefSums[y[i]][x[i]] = (int64_t) w[i];
	}

	for(int32_t j = 0; j < 2; j++) {
		for(int32_t i = 1; i < n; i++) {
			wPrefSums[i][j] += wPrefSums[i - 1][j];
		}
	}

	int64_t ans = 0;
	remax(ans, getWRangeSum(0, n, 1));
	remax(ans, getWRangeSum(0, n, 0));

	if(n > 2) {
		for(int32_t i = 0; i <= n; i++) {
			remax(ans, getWRangeSum(0, i, 0) + getWRangeSum(i, n, 1));
		}
	}

	return ans;
}

int64_t solveAllYs0(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> w) {
	const int32_t MAX_N = 1e5;

	std::array<int32_t, MAX_N + 1> wByColumn {};
	for(int32_t i = 0; i < m; i++) {
		wByColumn[x[i]] = w[i];
	}
	
	if(n == 2) {
		return std::max(wByColumn[0], wByColumn[1]);
	}

	std::array<std::array<std::array<int64_t, 2>, 2>, MAX_N + 1> dp {};
	dp[2][0][0] = 0;
	dp[2][0][1] = wByColumn[0] + wByColumn[2];
	dp[2][1][0] = wByColumn[1];
	dp[2][1][1] = wByColumn[2];
	for(int32_t j = 3; j <= n; j++) {
		dp[j][0][0] = std::max(dp[j - 1][0][0], dp[j - 1][1][0]);	
		dp[j][0][1] = std::max(dp[j - 1][0][0] + wByColumn[j - 2], dp[j - 1][1][0]) + wByColumn[j];
		dp[j][1][0] = std::max(dp[j - 1][0][1], dp[j - 1][1][1]);
		dp[j][1][1] = std::max(dp[j - 1][0][1], dp[j - 1][1][1]) + wByColumn[j] - wByColumn[j - 1];
	}

	return std::max(dp[n][0][0], dp[n][1][0]);
}

int64_t maxWeights(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
                      std::vector<int32_t> w) {
	if(n <= 300) {
		return solveSmallN(n, m, x, y, w);
	}
	else if(std::all_of(x.begin(), x.end(), [](int32_t v) { return !(v & 1); })) {
		return solveEvenXs(n, m, x, y, w);
	}
	else if(std::all_of(x.begin(), x.end(), [](int32_t v) { return (v < 2); })) {
		return solveAllXs0Or1(n, m, x, y, w);
	}
	else if(std::all_of(x.begin(), x.end(), [](int32_t v) { return (v == 0); })) {
		return solveAllYs0(n, m, x, w);
	}

	return 0;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	3048 KB	Output is correct
2	Correct	27 ms	3792 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	92 ms	10732 KB	Output is correct
6	Correct	99 ms	10852 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3028 KB	Output is correct
2	Correct	49 ms	7592 KB	Output is correct
3	Correct	63 ms	8920 KB	Output is correct
4	Correct	23 ms	3032 KB	Output is correct
5	Correct	31 ms	3780 KB	Output is correct
6	Correct	2 ms	3028 KB	Output is correct
7	Correct	2 ms	3028 KB	Output is correct
8	Correct	2 ms	3028 KB	Output is correct
9	Correct	2 ms	3028 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	27 ms	4720 KB	Output is correct
13	Correct	31 ms	5324 KB	Output is correct
14	Correct	25 ms	4708 KB	Output is correct
15	Correct	32 ms	4944 KB	Output is correct
16	Correct	27 ms	4708 KB	Output is correct
17	Correct	28 ms	4908 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	1st lines differ - on the 1st token, expected: '882019', found: '0'
3	Halted	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3028 KB	Output is correct
2	Correct	2 ms	3028 KB	Output is correct
3	Correct	1 ms	3028 KB	Output is correct
4	Correct	3 ms	3028 KB	Output is correct
5	Correct	2 ms	3028 KB	Output is correct
6	Correct	2 ms	3096 KB	Output is correct
7	Correct	2 ms	3028 KB	Output is correct
8	Correct	2 ms	3028 KB	Output is correct
9	Correct	13 ms	3144 KB	Output is correct
10	Correct	89 ms	3188 KB	Output is correct
11	Correct	10 ms	3156 KB	Output is correct
12	Correct	85 ms	3164 KB	Output is correct
13	Correct	4 ms	3132 KB	Output is correct
14	Correct	72 ms	3156 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3028 KB	Output is correct
2	Correct	2 ms	3028 KB	Output is correct
3	Correct	1 ms	3028 KB	Output is correct
4	Correct	3 ms	3028 KB	Output is correct
5	Correct	2 ms	3028 KB	Output is correct
6	Correct	2 ms	3096 KB	Output is correct
7	Correct	2 ms	3028 KB	Output is correct
8	Correct	2 ms	3028 KB	Output is correct
9	Correct	13 ms	3144 KB	Output is correct
10	Correct	89 ms	3188 KB	Output is correct
11	Correct	10 ms	3156 KB	Output is correct
12	Correct	85 ms	3164 KB	Output is correct
13	Correct	4 ms	3132 KB	Output is correct
14	Correct	72 ms	3156 KB	Output is correct
15	Correct	81 ms	3028 KB	Output is correct
16	Correct	4 ms	3132 KB	Output is correct
17	Correct	84 ms	5460 KB	Output is correct
18	Correct	134 ms	5432 KB	Output is correct
19	Correct	84 ms	5432 KB	Output is correct
20	Correct	84 ms	5432 KB	Output is correct
21	Correct	85 ms	5440 KB	Output is correct
22	Correct	94 ms	7736 KB	Output is correct
23	Correct	71 ms	3540 KB	Output is correct
24	Correct	76 ms	4660 KB	Output is correct
25	Correct	71 ms	3168 KB	Output is correct
26	Correct	127 ms	3540 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3028 KB	Output is correct
2	Correct	2 ms	3028 KB	Output is correct
3	Correct	1 ms	3028 KB	Output is correct
4	Correct	3 ms	3028 KB	Output is correct
5	Correct	2 ms	3028 KB	Output is correct
6	Correct	2 ms	3096 KB	Output is correct
7	Correct	2 ms	3028 KB	Output is correct
8	Correct	2 ms	3028 KB	Output is correct
9	Correct	13 ms	3144 KB	Output is correct
10	Correct	89 ms	3188 KB	Output is correct
11	Correct	10 ms	3156 KB	Output is correct
12	Correct	85 ms	3164 KB	Output is correct
13	Correct	4 ms	3132 KB	Output is correct
14	Correct	72 ms	3156 KB	Output is correct
15	Correct	81 ms	3028 KB	Output is correct
16	Correct	4 ms	3132 KB	Output is correct
17	Correct	84 ms	5460 KB	Output is correct
18	Correct	134 ms	5432 KB	Output is correct
19	Correct	84 ms	5432 KB	Output is correct
20	Correct	84 ms	5432 KB	Output is correct
21	Correct	85 ms	5440 KB	Output is correct
22	Correct	94 ms	7736 KB	Output is correct
23	Correct	71 ms	3540 KB	Output is correct
24	Correct	76 ms	4660 KB	Output is correct
25	Correct	71 ms	3168 KB	Output is correct
26	Correct	127 ms	3540 KB	Output is correct
27	Incorrect	2 ms	340 KB	1st lines differ - on the 1st token, expected: '2999', found: '0'
28	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	1st lines differ - on the 1st token, expected: '882019', found: '0'
3	Halted	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	3048 KB	Output is correct
2	Correct	27 ms	3792 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	92 ms	10732 KB	Output is correct
6	Correct	99 ms	10852 KB	Output is correct
7	Correct	3 ms	3028 KB	Output is correct
8	Correct	49 ms	7592 KB	Output is correct
9	Correct	63 ms	8920 KB	Output is correct
10	Correct	23 ms	3032 KB	Output is correct
11	Correct	31 ms	3780 KB	Output is correct
12	Correct	2 ms	3028 KB	Output is correct
13	Correct	2 ms	3028 KB	Output is correct
14	Correct	2 ms	3028 KB	Output is correct
15	Correct	2 ms	3028 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	27 ms	4720 KB	Output is correct
19	Correct	31 ms	5324 KB	Output is correct
20	Correct	25 ms	4708 KB	Output is correct
21	Correct	32 ms	4944 KB	Output is correct
22	Correct	27 ms	4708 KB	Output is correct
23	Correct	28 ms	4908 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Incorrect	0 ms	212 KB	1st lines differ - on the 1st token, expected: '882019', found: '0'
26	Halted	0 ms	0 KB	-

Submission #627293

Compilation message