oj.uz

Submission #626722

# Submission time Handle Problem Language Result Execution time Memory
626722 2022-08-11T17:11:00 Z JustInCase Catfish Farm (IOI22_fish) C++17
38 / 100
 111 ms 11200 KB 
#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 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 23 ms 3028 KB Output is correct
2 Correct 31 ms 3912 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 105 ms 11200 KB Output is correct
6 Correct 111 ms 11148 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 Incorrect 58 ms 4244 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '0'
3 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 0 ms 212 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 1 ms 3028 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 1 ms 3028 KB Output is correct
8 Correct 2 ms 3116 KB Output is correct
9 Correct 11 ms 3156 KB Output is correct
10 Correct 77 ms 3232 KB Output is correct
11 Correct 11 ms 3156 KB Output is correct
12 Correct 71 ms 3176 KB Output is correct
13 Correct 3 ms 3028 KB Output is correct
14 Correct 73 ms 3156 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 1 ms 3028 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 1 ms 3028 KB Output is correct
8 Correct 2 ms 3116 KB Output is correct
9 Correct 11 ms 3156 KB Output is correct
10 Correct 77 ms 3232 KB Output is correct
11 Correct 11 ms 3156 KB Output is correct
12 Correct 71 ms 3176 KB Output is correct
13 Correct 3 ms 3028 KB Output is correct
14 Correct 73 ms 3156 KB Output is correct
15 Correct 70 ms 3116 KB Output is correct
16 Correct 4 ms 3128 KB Output is correct
17 Correct 84 ms 4936 KB Output is correct
18 Correct 80 ms 4960 KB Output is correct
19 Correct 84 ms 4900 KB Output is correct
20 Correct 78 ms 4960 KB Output is correct
21 Correct 95 ms 4956 KB Output is correct
22 Correct 93 ms 6556 KB Output is correct
23 Correct 72 ms 3572 KB Output is correct
24 Correct 97 ms 4416 KB Output is correct
25 Correct 70 ms 3168 KB Output is correct
26 Correct 71 ms 3540 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 1 ms 3028 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 1 ms 3028 KB Output is correct
8 Correct 2 ms 3116 KB Output is correct
9 Correct 11 ms 3156 KB Output is correct
10 Correct 77 ms 3232 KB Output is correct
11 Correct 11 ms 3156 KB Output is correct
12 Correct 71 ms 3176 KB Output is correct
13 Correct 3 ms 3028 KB Output is correct
14 Correct 73 ms 3156 KB Output is correct
15 Correct 70 ms 3116 KB Output is correct
16 Correct 4 ms 3128 KB Output is correct
17 Correct 84 ms 4936 KB Output is correct
18 Correct 80 ms 4960 KB Output is correct
19 Correct 84 ms 4900 KB Output is correct
20 Correct 78 ms 4960 KB Output is correct
21 Correct 95 ms 4956 KB Output is correct
22 Correct 93 ms 6556 KB Output is correct
23 Correct 72 ms 3572 KB Output is correct
24 Correct 97 ms 4416 KB Output is correct
25 Correct 70 ms 3168 KB Output is correct
26 Correct 71 ms 3540 KB Output is correct
27 Incorrect 1 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 Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3028 KB Output is correct
2 Correct 31 ms 3912 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 105 ms 11200 KB Output is correct
6 Correct 111 ms 11148 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Incorrect 58 ms 4244 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '0'
9 Halted 0 ms 0 KB -