Submission #833328

#	Time	Username	Problem	Language	Result	Execution time	Memory
833328		pavement	Catfish Farm (IOI22_fish)	C++17	61 / 100	1089 ms	58272 KiB

fish

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

#define eb emplace_back
#define mp make_pair

using ll = long long;
using ii = pair<int, int>;

int N, M;
vector<int> X, Y, W;
vector<vector<ll> > mem;
vector<ii> col[100005];

ll dp(int p, int ty) {
	ll ret = 0;
	if (ty == 0) {
		if (p == 0) {
			return 0;
		}
		if (p < 0) {
			return -(ll)1e16;
		}
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		ret = max({ret, dp(p - 1, 0), dp(p - 1, 1)});
		if (p && !col[p - 1].empty()) {
			ret = max(ret, dp(col[p - 1][0].second, 2));
		}
	} else if (ty == 1) {
		if (p == 0) {
			return 0;
		}
		if (p < 0) {
			return -(ll)1e16;
		}
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		ret = max({ret, dp(p - 1, 0), dp(p - 1, 1)});
		if (p && !col[p - 1].empty()) {
			ret = max(ret, dp(col[p - 1][0].second, 2));
			ret = max(ret, dp(col[p - 1].back().second, 3));
		}
	} else if (ty == 2) {
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		int x = X[p], y = Y[p];
		ll sum_all = 0;
		int ptr = lower_bound(col[x].begin(), col[x].end(), mp(y, p)) - col[x].begin();
		assert(ptr != (int)col[x].size());
		for (int i = ptr; i < (int)col[x].size(); i++) {
			sum_all += W[col[x][i].second];
		}
		ret = max(ret, dp(x - 1, 1) + sum_all);
		if (x && !col[x - 1].empty()) {
			ll sum_cur = 0;
			for (auto [y_p, idx_p] : col[x - 1]) {
				if (y_p <= y) {
					continue;
				}
				while (ptr < (int)col[x].size() && y_p > Y[col[x][ptr].second]) {
					sum_cur += W[col[x][ptr].second];
					ptr++;
				}
				ret = max(ret, dp(idx_p, 2) + sum_cur);
			}
		}
	} else {
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		int x = X[p], y = Y[p];
		ll sum_all = 0;
		int ptr = lower_bound(col[x].begin(), col[x].end(), mp(y, p)) - col[x].begin();
		assert(ptr != (int)col[x].size());
		for (int i = ptr; i >= 0; i--) {
			sum_all += W[col[x][i].second];
		}
		ret = max(ret, dp(x, 0) + sum_all);
		if (x && !col[x - 1].empty()) {
			ll sum_cur = 0;
			for (int _ = (int)col[x - 1].size() - 1; _ >= 0; _--) {
				auto [y_p, idx_p] = col[x - 1][_];
				if (y_p >= y) {
					continue;
				}
				while (ptr >= 0 && y_p < Y[col[x][ptr].second]) {
					sum_cur += W[col[x][ptr].second];
					ptr--;
				}
				//~ cout << "DP " << p << ' ' << ty << " TO " << idx_p << ' ' << 3 << ' ' << sum_cur << ' ' << y_p << ' ' << y << '\n';
				ret = max(ret, dp(idx_p, 3) + sum_cur);
			}
		}
	}
	//~ cout << "DP " << p << ' ' << ty << ' ' << ret << '\n';
	return mem[p][ty] = ret;
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	::N = N;
	::M = M;
	::X = X;
	::Y = Y;
	::W = W;
	mem = vector<vector<ll> >(N + M, vector<ll>(4, -1));
	for (int i = 0; i < M; i++) {
		col[X[i]].eb(Y[i], i);
	}
	for (int i = 0; i < N; i++) {
		sort(col[i].begin(), col[i].end());
	}
	return dp(N, 0);
}

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