Submission #626238

#	Time	Username	Problem	Language	Result	Execution time	Memory
626238		Temmie	Catfish Farm (IOI22_fish)	C++17	100 / 100	275 ms	52400 KiB

fish

#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].first) {
			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 - 2][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][nnxt + 1].first < of[i][j].first) {
					nnxt++;
				}
				dp[i][0][j] = std::max(dp[i][0][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] }) - (j ? pre[i][j - 1] : 0LL));
				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: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16