oj.uz

Submission #626147

# Submission time Handle Problem Language Result Execution time Memory
626147 2022-08-11T09:03:34 Z Temmie Catfish Farm (IOI22_fish) C++17
9 / 100
 287 ms 104772 KB 
#include <bits/stdc++.h>

long long max_weights(int n, int m, std::vector <int> _x, std::vector <int> _y, std::vector <int> _w) {
	std::vector <std::vector <std::pair <int, int>>> of(n);
	for (int i = 0; i < m; i++) {
		of[_x[i]].emplace_back(_y[i], _w[i]);
	}
	for (int i = 0; i < n; i++) {
		of[i].emplace_back(0, 0);
		of[i].emplace_back(n, 0);
		std::sort(of[i].begin(), of[i].end());
		if (of[i][1].second) {
			of[i].erase(of[i].begin());
		}
	}
	std::vector <std::vector <std::vector <long long>>> dp(n, std::vector <std::vector <long long>> (3));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			dp[i][j].resize(of[i].size());
		}
	}
	std::vector <std::vector <long long>> pre(n);
	for (int i = 0; i < n; i++) {
		pre[i].resize(of[i].size());
		pre[i][0] = of[i][0].second;
		for (int j = 1; j < (int) of[i].size(); j++) {
			pre[i][j] = pre[i][j - 1] + of[i][j].second;
		}
	}
	dp[0][0].assign(dp[0][0].size(), 0);
	for (int nxt = 0, j = 1; j < (int) of[0].size(); j++) {
		while (nxt + 1 < (int) of[1].size() && of[1][nxt + 1].first < of[0][j].first) {
			nxt++;
		}
		dp[0][1][j] = pre[1][nxt];
	}
	for (int i = 1; i < n; i++) {
		std::vector <long long> pre_mx0(dp[i - 1][0].size());
		pre_mx0[0] = dp[i - 1][0][0];
		for (int j = 1; j < (int) dp[i - 1][0].size(); j++) {
			pre_mx0[j] = std::max(dp[i - 1][0][j], pre_mx0[j - 1]);
		}
		std::vector <long long> suf_mx[2];
		for (int k = 0; k <= 1; k++) {
			suf_mx[k].resize(dp[i - 1][k + 1].size());
			suf_mx[k].back() = dp[i - 1][k + 1].back();
			for (int j = (int) dp[i - 1][k + 1].size() - 2; j >= 0; j--) {
				suf_mx[k][j] = std::max(dp[i - 1][k + 1][j], suf_mx[k][j + 1]);
			}
		}
		std::vector <long long> psuf_mx[2];
		std::vector <long long> ppre_mx[2];
		for (int k = 0; k <= 1; k++) {
			psuf_mx[k].resize(i > 1 ? dp[i - 2][k + 1].size() : 1, 0);
			if (i > 1) {
				ppre_mx[k].resize(dp[i - 2][k + 1].size());
				for (int ptr = 0, j = 0; j < (int) dp[i - 1][k + 1].size(); j++) {
					while (ptr + 1 < (int) of[i - 1].size() && of[i - 1][ptr + 1].first < of[i - 2][j].first) {
						ptr++;
					}
					ppre_mx[k][j] = dp[i - 2][k + 1][j] - pre[i - 1][ptr];
					if (j) {
						ppre_mx[k][j] = std::max(ppre_mx[k][j], ppre_mx[k][j - 1]);
					}
				}
				psuf_mx[k].back() = dp[i - 2][k + 1].back();
				for (int j = (int) dp[i - 2][k + 1].size() - 2; j >= 0; j--) {
					psuf_mx[k][j] = std::max(dp[i - 2][k + 1][j], psuf_mx[k][j + 1]);
				}
			}
		}
		dp[i][0][0] = dp[i][0][0] = std::max({ pre_mx0[0], psuf_mx[0][0], psuf_mx[1][0] });
		dp[i][1][0] = pre_mx0[0];
		dp[i][2][0] = std::max(suf_mx[0][0], suf_mx[1][0]);
		if (i > 1) {
			for (int prv = 0, nxt = 0, nnxt = 0, j = 0; j < (int) dp[i][0].size(); j++) {
				while (prv + 1 < (int) of[i - 2].size() && of[i - 2][prv + 1].first < of[i][j].first) {
					prv++;
				}
				while (nxt + 1 < (int) of[i - 1].size() && of[i - 1][nxt + 1].first < of[i][j].first) {
					nxt++;
				}
				while (i + 1 < n && nnxt + 1 < (int) of[i + 1].size() && of[i + 1][nxt + 1].first < of[i][j].first) {
					nnxt++;
				}
				dp[i][0][j] = std::max({ dp[i][0][j], ppre_mx[0][prv] + pre[i - 1][nxt],
				ppre_mx[1][prv] + pre[i - 1][nxt], psuf_mx[0][prv], psuf_mx[1][prv] });
				dp[i][1][j] = std::max(dp[i][1][j], std::max({ ppre_mx[0][prv] + pre[i - 1][nxt],
				ppre_mx[1][prv] + pre[i - 1][nxt], psuf_mx[0][prv], psuf_mx[1][prv] }) + (i + 1 < n ? pre[i + 1][nnxt] : 0LL));
			}
		}
		for (int prv = 0, nxt = 0, j = 1; j < (int) of[i].size(); j++) {
			while (prv + 1 < (int) of[i - 1].size() && of[i - 1][prv + 1].first < of[i][j].first) {
				prv++;
			}
			while (i + 1 < n && nxt + 1 < (int) of[i + 1].size() && of[i + 1][nxt + 1].first < of[i][j].first) {
				nxt++;
			}
			dp[i][0][j] = std::max(dp[i][0][j], pre_mx0[prv] + pre[i - 1][prv] - pre[i][j - 1]);
			dp[i][1][j] = std::max(dp[i][1][j], pre_mx0[prv] + pre[i - 1][prv] + (i + 1 < n ? pre[i + 1][nxt] : 0LL));
			dp[i][2][j] = std::max(
			suf_mx[0][prv] + (i + 1 < n ? pre[i + 1][nxt] : 0LL) - pre[i][j - 1],
			suf_mx[1][prv] + (i + 1 < n ? pre[i + 1][nxt] : 0LL) - pre[i][j - 1]);
		}
	}
	long long ans = 0;
	for (int k = 0; k < 3; k++) {
		for (long long x : dp[n - 1][k]) {
			ans = std::max(ans, x);
		}
	}
	return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 35288 KB Output is correct
2 Correct 160 ms 40180 KB Output is correct
3 Correct 112 ms 30744 KB Output is correct
4 Correct 88 ms 30796 KB Output is correct
5 Runtime error 287 ms 104772 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 30816 KB Output is correct
2 Correct 95 ms 30824 KB Output is correct
3 Correct 111 ms 29900 KB Output is correct
4 Correct 149 ms 32204 KB Output is correct
5 Correct 146 ms 35228 KB Output is correct
6 Correct 154 ms 35368 KB Output is correct
7 Correct 145 ms 35252 KB Output is correct
8 Correct 157 ms 35256 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 30816 KB Output is correct
2 Correct 95 ms 30824 KB Output is correct
3 Correct 111 ms 29900 KB Output is correct
4 Correct 149 ms 32204 KB Output is correct
5 Correct 146 ms 35228 KB Output is correct
6 Correct 154 ms 35368 KB Output is correct
7 Correct 145 ms 35252 KB Output is correct
8 Correct 157 ms 35256 KB Output is correct
9 Incorrect 146 ms 35148 KB 1st lines differ - on the 1st token, expected: '99999', found: '66666'
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 35288 KB Output is correct
2 Correct 160 ms 40180 KB Output is correct
3 Correct 112 ms 30744 KB Output is correct
4 Correct 88 ms 30796 KB Output is correct
5 Runtime error 287 ms 104772 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -