Submission #626692

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
626692	2022-08-11T16:14:01 Z	JustInCase	Catfish Farm (IOI22_fish)	C++17	3 / 100	85 ms	10856 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 (int64_t) 0;
		}

		assert(column < MAX_N);
		assert(startRow <= MAX_N && endRow <= MAX_N);
		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 solveAllX0Or1(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
			std::vector<int32_t> w) {
	std::array<std::array<int64_t, MAX_N>, 2> wPrefSums;

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

		assert(column < MAX_N);
		assert(startRow <= MAX_N && endRow <= MAX_N);
		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];
		}
	}


}
*/

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);
	}

	return 0;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	3028 KB	Output is correct
2	Correct	26 ms	3788 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	83 ms	10828 KB	Output is correct
6	Correct	85 ms	10856 KB	Output is correct

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3028 KB	Output is correct
2	Incorrect	42 ms	3992 KB	1st lines differ - on the 1st token, expected: '40604614618209', found: '0'
3	Halted	0 ms	0 KB	-

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
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3028 KB	Output is correct
2	Correct	1 ms	3028 KB	Output is correct
3	Correct	2 ms	3028 KB	Output is correct
4	Correct	2 ms	3088 KB	Output is correct
5	Correct	2 ms	3028 KB	Output is correct
6	Correct	2 ms	3028 KB	Output is correct
7	Correct	1 ms	3044 KB	Output is correct
8	Correct	1 ms	3028 KB	Output is correct
9	Correct	11 ms	3144 KB	Output is correct
10	Incorrect	80 ms	3192 KB	1st lines differ - on the 1st token, expected: '799839985182', found: '8030604434741355055'
11	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3028 KB	Output is correct
2	Correct	1 ms	3028 KB	Output is correct
3	Correct	2 ms	3028 KB	Output is correct
4	Correct	2 ms	3088 KB	Output is correct
5	Correct	2 ms	3028 KB	Output is correct
6	Correct	2 ms	3028 KB	Output is correct
7	Correct	1 ms	3044 KB	Output is correct
8	Correct	1 ms	3028 KB	Output is correct
9	Correct	11 ms	3144 KB	Output is correct
10	Incorrect	80 ms	3192 KB	1st lines differ - on the 1st token, expected: '799839985182', found: '8030604434741355055'
11	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3028 KB	Output is correct
2	Correct	1 ms	3028 KB	Output is correct
3	Correct	2 ms	3028 KB	Output is correct
4	Correct	2 ms	3088 KB	Output is correct
5	Correct	2 ms	3028 KB	Output is correct
6	Correct	2 ms	3028 KB	Output is correct
7	Correct	1 ms	3044 KB	Output is correct
8	Correct	1 ms	3028 KB	Output is correct
9	Correct	11 ms	3144 KB	Output is correct
10	Incorrect	80 ms	3192 KB	1st lines differ - on the 1st token, expected: '799839985182', found: '8030604434741355055'
11	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	21 ms	3028 KB	Output is correct
2	Correct	26 ms	3788 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	83 ms	10828 KB	Output is correct
6	Correct	85 ms	10856 KB	Output is correct
7	Correct	1 ms	3028 KB	Output is correct
8	Incorrect	42 ms	3992 KB	1st lines differ - on the 1st token, expected: '40604614618209', found: '0'
9	Halted	0 ms	0 KB	-

Submission #626692

Compilation message