oj.uz

Submission #630319

# Submission time Handle Problem Language Result Execution time Memory
630319 2022-08-16T07:42:02 Z JustInCase Catfish Farm (IOI22_fish) C++17
12 / 100
 88 ms 70816 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++) {
		int64_t pref = 0;
		for(int32_t k = 0; k <= n; k++) {
			remax(pref, dpIncr[k] - getWRangeSum(0, k, j - 1));
			nDpIncr[k] = std::max(pref + getWRangeSum(0, k, j - 1), dpDecr[0]);
		}

		int64_t suff = 0;
		for(int32_t k = n; k >= 0; k--) {
			remax(suff, std::max(dpIncr[k], dpDecr[k]) + getWRangeSum(0, k, j));
			nDpDecr[k] = suff - getWRangeSum(0, k, j);
		}

		std::swap(nDpIncr, dpIncr);
		std::swap(nDpDecr, dpDecr);
	}

	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 3156 KB Output is correct
2 Correct 26 ms 3792 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 84 ms 10852 KB Output is correct
6 Correct 88 ms 10852 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70816 KB Output is correct
2 Correct 48 ms 7500 KB Output is correct
3 Correct 64 ms 8920 KB Output is correct
4 Correct 21 ms 3048 KB Output is correct
5 Correct 28 ms 3792 KB Output is correct
6 Incorrect 34 ms 70788 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 16 ms 5460 KB Output is correct
4 Correct 14 ms 4964 KB Output is correct
5 Correct 27 ms 6860 KB Output is correct
6 Correct 24 ms 6856 KB Output is correct
7 Correct 41 ms 6848 KB Output is correct
8 Correct 39 ms 6848 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 70816 KB Output is correct
2 Correct 36 ms 70804 KB Output is correct
3 Incorrect 33 ms 70704 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 35 ms 70816 KB Output is correct
2 Correct 36 ms 70804 KB Output is correct
3 Incorrect 33 ms 70704 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 35 ms 70816 KB Output is correct
2 Correct 36 ms 70804 KB Output is correct
3 Incorrect 33 ms 70704 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 16 ms 5460 KB Output is correct
4 Correct 14 ms 4964 KB Output is correct
5 Correct 27 ms 6860 KB Output is correct
6 Correct 24 ms 6856 KB Output is correct
7 Correct 41 ms 6848 KB Output is correct
8 Correct 39 ms 6848 KB Output is correct
9 Incorrect 24 ms 2640 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 3156 KB Output is correct
2 Correct 26 ms 3792 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 84 ms 10852 KB Output is correct
6 Correct 88 ms 10852 KB Output is correct
7 Correct 38 ms 70816 KB Output is correct
8 Correct 48 ms 7500 KB Output is correct
9 Correct 64 ms 8920 KB Output is correct
10 Correct 21 ms 3048 KB Output is correct
11 Correct 28 ms 3792 KB Output is correct
12 Incorrect 34 ms 70788 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
13 Halted 0 ms 0 KB -