oj.uz

Submission #626669

# Submission time Handle Problem Language Result Execution time Memory
626669 2022-08-11T15:41:46 Z JustInCase Catfish Farm (IOI22_fish) C++17
3 / 100
 85 ms 10852 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 + 2>, 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;
		}

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

Compilation message

fish.cpp: In function 'int64_t max_weights(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:99:1: warning: control reaches end of non-void function [-Wreturn-type]
   99 | }
      | ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3028 KB Output is correct
2 Correct 35 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 84 ms 10828 KB Output is correct
6 Correct 85 ms 10852 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 48 ms 5920 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
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 Correct 0 ms 212 KB Output is correct
3 Incorrect 16 ms 2200 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 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 3028 KB Output is correct
9 Correct 14 ms 3028 KB Output is correct
10 Incorrect 71 ms 3204 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 2 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 1 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 3028 KB Output is correct
9 Correct 14 ms 3028 KB Output is correct
10 Incorrect 71 ms 3204 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 2 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 1 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 3028 KB Output is correct
9 Correct 14 ms 3028 KB Output is correct
10 Incorrect 71 ms 3204 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '8030604434741355055'
11 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 0 ms 212 KB Output is correct
3 Incorrect 16 ms 2200 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3028 KB Output is correct
2 Correct 35 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 84 ms 10828 KB Output is correct
6 Correct 85 ms 10852 KB Output is correct
7 Correct 1 ms 3028 KB Output is correct
8 Incorrect 48 ms 5920 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
9 Halted 0 ms 0 KB -