Submission #627182

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
627182	2022-08-12T10:45:57 Z	JustInCase	Catfish Farm (IOI22_fish)	C++17	38 / 100	111 ms	10864 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 (int64_t) 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 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 {
		return solveAllXs0Or1(n, m, x, y, w);
	}

	return 0;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	3156 KB	Output is correct
2	Correct	28 ms	3788 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	86 ms	10864 KB	Output is correct
6	Correct	102 ms	10852 KB	Output is correct

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3028 KB	Output is correct
2	Correct	46 ms	7500 KB	Output is correct
3	Correct	59 ms	8920 KB	Output is correct
4	Correct	21 ms	3044 KB	Output is correct
5	Correct	30 ms	3788 KB	Output is correct
6	Correct	2 ms	3028 KB	Output is correct
7	Correct	2 ms	3028 KB	Output is correct
8	Correct	1 ms	3028 KB	Output is correct
9	Correct	2 ms	3028 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	27 ms	4692 KB	Output is correct
13	Incorrect	28 ms	5332 KB	1st lines differ - on the 1st token, expected: '49960364197170', found: '8031590577832682814'
14	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3028 KB	Output is correct
2	Correct	2 ms	3124 KB	Output is correct
3	Correct	2 ms	3012 KB	Output is correct
4	Correct	2 ms	3028 KB	Output is correct
5	Correct	2 ms	3108 KB	Output is correct
6	Correct	2 ms	3028 KB	Output is correct
7	Correct	2 ms	3028 KB	Output is correct
8	Correct	3 ms	3028 KB	Output is correct
9	Correct	10 ms	3028 KB	Output is correct
10	Correct	80 ms	3188 KB	Output is correct
11	Correct	10 ms	3028 KB	Output is correct
12	Correct	68 ms	3156 KB	Output is correct
13	Correct	2 ms	3028 KB	Output is correct
14	Correct	68 ms	3100 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3028 KB	Output is correct
2	Correct	2 ms	3124 KB	Output is correct
3	Correct	2 ms	3012 KB	Output is correct
4	Correct	2 ms	3028 KB	Output is correct
5	Correct	2 ms	3108 KB	Output is correct
6	Correct	2 ms	3028 KB	Output is correct
7	Correct	2 ms	3028 KB	Output is correct
8	Correct	3 ms	3028 KB	Output is correct
9	Correct	10 ms	3028 KB	Output is correct
10	Correct	80 ms	3188 KB	Output is correct
11	Correct	10 ms	3028 KB	Output is correct
12	Correct	68 ms	3156 KB	Output is correct
13	Correct	2 ms	3028 KB	Output is correct
14	Correct	68 ms	3100 KB	Output is correct
15	Correct	67 ms	3120 KB	Output is correct
16	Correct	3 ms	3156 KB	Output is correct
17	Correct	97 ms	4740 KB	Output is correct
18	Correct	80 ms	4704 KB	Output is correct
19	Correct	78 ms	4692 KB	Output is correct
20	Correct	77 ms	4704 KB	Output is correct
21	Correct	79 ms	4704 KB	Output is correct
22	Correct	111 ms	6228 KB	Output is correct
23	Correct	73 ms	3416 KB	Output is correct
24	Correct	80 ms	4180 KB	Output is correct
25	Correct	68 ms	3156 KB	Output is correct
26	Correct	72 ms	3412 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3028 KB	Output is correct
2	Correct	2 ms	3124 KB	Output is correct
3	Correct	2 ms	3012 KB	Output is correct
4	Correct	2 ms	3028 KB	Output is correct
5	Correct	2 ms	3108 KB	Output is correct
6	Correct	2 ms	3028 KB	Output is correct
7	Correct	2 ms	3028 KB	Output is correct
8	Correct	3 ms	3028 KB	Output is correct
9	Correct	10 ms	3028 KB	Output is correct
10	Correct	80 ms	3188 KB	Output is correct
11	Correct	10 ms	3028 KB	Output is correct
12	Correct	68 ms	3156 KB	Output is correct
13	Correct	2 ms	3028 KB	Output is correct
14	Correct	68 ms	3100 KB	Output is correct
15	Correct	67 ms	3120 KB	Output is correct
16	Correct	3 ms	3156 KB	Output is correct
17	Correct	97 ms	4740 KB	Output is correct
18	Correct	80 ms	4704 KB	Output is correct
19	Correct	78 ms	4692 KB	Output is correct
20	Correct	77 ms	4704 KB	Output is correct
21	Correct	79 ms	4704 KB	Output is correct
22	Correct	111 ms	6228 KB	Output is correct
23	Correct	73 ms	3416 KB	Output is correct
24	Correct	80 ms	4180 KB	Output is correct
25	Correct	68 ms	3156 KB	Output is correct
26	Correct	72 ms	3412 KB	Output is correct
27	Incorrect	1 ms	1876 KB	1st lines differ - on the 1st token, expected: '2999', found: '1001'
28	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	3156 KB	Output is correct
2	Correct	28 ms	3788 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	86 ms	10864 KB	Output is correct
6	Correct	102 ms	10852 KB	Output is correct
7	Correct	2 ms	3028 KB	Output is correct
8	Correct	46 ms	7500 KB	Output is correct
9	Correct	59 ms	8920 KB	Output is correct
10	Correct	21 ms	3044 KB	Output is correct
11	Correct	30 ms	3788 KB	Output is correct
12	Correct	2 ms	3028 KB	Output is correct
13	Correct	2 ms	3028 KB	Output is correct
14	Correct	1 ms	3028 KB	Output is correct
15	Correct	2 ms	3028 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	27 ms	4692 KB	Output is correct
19	Incorrect	28 ms	5332 KB	1st lines differ - on the 1st token, expected: '49960364197170', found: '8031590577832682814'
20	Halted	0 ms	0 KB	-

Submission #627182

Compilation message