Submission #785390

#	Time	Username	Problem	Language	Result	Execution time	Memory
785390		khshg	Catfish Farm (IOI22_fish)	C++17	0 / 100	1064 ms	146464 KiB

fish

#include<bits/stdc++.h>
using namespace std;

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	vector<vector<int>> go(N);
	vector<vector<pair<int, int>>> Ws(N);
	for(int i = 0; i < M; ++i) {
		++Y[i];
		if(X[i] - 1 >= 0) go[X[i]].push_back(Y[i]);
		if(X[i] + 1 < N) go[X[i] + 1].push_back(Y[i]);
		Ws[X[i]].emplace_back(Y[i], W[i]);
	}
	for(auto& u : go) {
		u.push_back(0);
		sort(begin(u), end(u));
		u.erase(unique(begin(u), end(u)), end(u));
	}
	for(auto& u : Ws) {
		sort(begin(u), end(u));
		u.erase(unique(begin(u), end(u)), end(u));
		for(int i = 1; i < (int)u.size(); ++i) {
			u[i].second += u[i - 1].second;
		}
	}
	auto sum = [&](int x, int y) -> long long {
		if(x < 0 || x >= N) return 0;
		auto it = lower_bound(begin(Ws[x]), end(Ws[x]), make_pair(y, 0));
		if(it == end(Ws[x])) return 0;
		if((*it).first != y) return 0;
		return (*it).second;
	};
	vector<map<int, map<int, long long>>> dp(N);
	long long ans = 0;
	for(int i = 0; i < N; ++i) {
		for(int ci = 0; ci < (int)go[i].size(); ++ci) {
			int u = go[i][ci];
			if(i - 1 >= 0) for(int pi = 0; pi < (int)go[i - 1].size(); ++pi) {
				int v = go[i - 1][pi];
				if(i - 2 >= 0) for(int ppi = 0; ppi < (int)go[i - 2].size(); ++ppi) {
					int y = go[i - 2][ppi];
					long long pl = dp[i - 1][pi][ppi] + sum(i + 1, u) - sum(i, min(u, v)) + max(0LL, sum(i - 1, u) - sum(i - 1, max(v, y)));
					dp[i][ci][pi] = max(dp[i][ci][pi], pl);
					ans = max(ans, dp[i][ci][pi]);
				} else {
					dp[i][ci][pi] = dp[i - 1][pi][0] + sum(i + 1, u) - sum(i, min(u, v)) + max(0LL, sum(i - 1, u) - sum(i - 1, v));
					ans = max(ans, dp[i][ci][pi]);
				}
			} else {
				if(u == 0) continue;
				dp[i][ci][0] = sum(i - 1, u) + sum(i + 1, u);
				ans = max(ans, dp[i][ci][0]);
			}
		}
	}
	return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16