oj.uz

Submission #630297

# Submission time Handle Problem Language Result Execution time Memory
630297 2022-08-16T07:23:29 Z JustInCase Catfish Farm (IOI22_fish) C++17
12 / 100
 90 ms 70812 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 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 + 3> 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 + 3> dp {};
	dp[2][0][0] = 0;
	dp[2][0][1] = wByColumn[0];
	dp[2][1][0] = 0;
	dp[2][1][1] = 0;
	for(int32_t j = 2; j <= n + 1; j++) {
		for(int32_t p = 0; p < 2; p++) {
			for(int32_t q = 0; q < 2; q++) {
				remax(dp[j + 1][q][0], dp[j][p][q] + ((p == 1 && q != 1) ? wByColumn[j - 1] : 0));
				remax(dp[j + 1][q][1], dp[j][p][q] + (q != 1 ? wByColumn[j - 1] : 0));
			}
		}
	}

	return dp[n + 2][0][0];
}

int64_t solveMediumN(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 = 3000;

	std::array<std::array<int64_t, MAX_N>, 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 < n; j++) {
		for(int32_t i = 1; i < n; i++) {
			wPrefSums[i][j] += wPrefSums[i - 1][j];
		}
	}
	
	std::array<int64_t, MAX_N> dpIncr{}, dpDecr{}, nDpIncr{}, nDpDecr{};

	dpIncr.fill(-1e18);
	dpDecr.fill(-1e18);

	dpIncr[0] = 0;
	dpDecr[0] = 0;

	for(int32_t j = 1; j <= n; j++) {
		for(int32_t k = 0; k <= n; k++) {
			nDpIncr[k] = dpDecr[0];
			for(int32_t lastK = 0; lastK <= k; lastK++) {
				remax(nDpIncr[k], dpIncr[lastK] + getWRangeSum(lastK, k, j - 1));
			}

			nDpDecr[k] = -1e18;
			for(int32_t lastK = k; lastK <= n; lastK++) {
				remax(nDpDecr[k], dpDecr[lastK] + getWRangeSum(k, lastK, j));
				remax(nDpDecr[k], dpIncr[lastK] + getWRangeSum(k, lastK, j));
			}
		}

		dpIncr = nDpIncr;
		dpDecr = nDpDecr;
	}

	return std::max(dpIncr[0], dpDecr[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 <= 3000) {
		return solveMediumN(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(y.begin(), y.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 21 ms 3020 KB Output is correct
2 Correct 27 ms 3784 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 90 ms 10852 KB Output is correct
6 Correct 89 ms 10852 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 70736 KB Output is correct
2 Correct 46 ms 7584 KB Output is correct
3 Correct 56 ms 8800 KB Output is correct
4 Correct 21 ms 3020 KB Output is correct
5 Correct 27 ms 3796 KB Output is correct
6 Incorrect 40 ms 70812 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
7 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 17 ms 5420 KB Output is correct
4 Correct 12 ms 4964 KB Output is correct
5 Correct 28 ms 6848 KB Output is correct
6 Correct 22 ms 6852 KB Output is correct
7 Correct 27 ms 6856 KB Output is correct
8 Correct 26 ms 6836 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70740 KB Output is correct
2 Correct 37 ms 70756 KB Output is correct
3 Incorrect 35 ms 70784 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70740 KB Output is correct
2 Correct 37 ms 70756 KB Output is correct
3 Incorrect 35 ms 70784 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70740 KB Output is correct
2 Correct 37 ms 70756 KB Output is correct
3 Incorrect 35 ms 70784 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 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 Correct 2 ms 3796 KB Output is correct
3 Correct 17 ms 5420 KB Output is correct
4 Correct 12 ms 4964 KB Output is correct
5 Correct 28 ms 6848 KB Output is correct
6 Correct 22 ms 6852 KB Output is correct
7 Correct 27 ms 6856 KB Output is correct
8 Correct 26 ms 6836 KB Output is correct
9 Incorrect 27 ms 2636 KB 1st lines differ - on the 1st token, expected: '99999', found: '0'
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3020 KB Output is correct
2 Correct 27 ms 3784 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 90 ms 10852 KB Output is correct
6 Correct 89 ms 10852 KB Output is correct
7 Correct 41 ms 70736 KB Output is correct
8 Correct 46 ms 7584 KB Output is correct
9 Correct 56 ms 8800 KB Output is correct
10 Correct 21 ms 3020 KB Output is correct
11 Correct 27 ms 3796 KB Output is correct
12 Incorrect 40 ms 70812 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
13 Halted 0 ms 0 KB -