Submission #833381

#	Time	Username	Problem	Language	Result	Execution time	Memory
833381		pavement	Catfish Farm (IOI22_fish)	C++17	100 / 100	163 ms	55552 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>;

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	auto tmp = vector<ll>(N + M), tmp2 = vector<ll>(N + M);
	auto dp = vector<vector<ll> >(N + M, vector<ll>(4, 0));
	auto col = vector<vector<ii> >(N);
	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());
	}
	for (int i = 0; i <= N; i++) {
		{
			// ty == 0
			if (i > 0) {
				dp[i][0] = max({0ll, dp[i - 1][0], dp[i - 1][1]});
			} else {
				dp[i][0] = 0;
			}
			if (i && !col[i - 1].empty()) {
				dp[i][0] = max(dp[i][0], dp[col[i - 1][0].second][2]);
			}
		}
		{
			// ty == 1
			if (i > 0) {
				dp[i][1] = max({0ll, dp[i - 1][0], dp[i - 1][1]});
			} else {
				dp[i][1] = 0;
			}
			if (i && !col[i - 1].empty()) {
				dp[i][1] = max(dp[i][1], dp[col[i - 1][0].second][2]);
				dp[i][1] = max(dp[i][1], dp[col[i - 1].back().second][3]);
			}
		}
		if (i < N) {
			// ty == 2
			{
				ll sum_all = 0;
				for (int _ = (int)col[i].size() - 1; _ >= 0; _--) {
					int p = col[i][_].second, x = X[p];
					sum_all += W[p];
					if (x - 1 >= 0) {
						dp[p][2] = max(dp[p][2], dp[x - 1][1] + sum_all);
					}
				}
				if (i && !col[i - 1].empty()) {
					int ptr = 0;
					ll pf_sum = 0;
					for (int _ = 0; _ < (int)col[i - 1].size(); _++) {
						while (ptr < (int)col[i].size() && col[i - 1][_].first > col[i][ptr].first) {
							pf_sum += W[col[i][ptr].second];
							ptr++;
						}
						tmp[_] = pf_sum;
					}
					pf_sum = 0;
					for (int _ = 0; _ < (int)col[i].size(); _++) {
						tmp2[_] = pf_sum;
						pf_sum += W[col[i][_].second];
					}
					ptr = (int)col[i - 1].size() - 1;
					ll rs = -(ll)1e16;
					for (int _ = (int)col[i].size() - 1; _ >= 0; _--) {
						while (ptr >= 0 && col[i - 1][ptr].first > col[i][_].first) {
							rs = max(rs, dp[col[i - 1][ptr].second][2] + tmp[ptr]);
							ptr--;
						}
						dp[col[i][_].second][2] = max(dp[col[i][_].second][2], rs - tmp2[_]);
					}
				}
			}
			// ty == 3
			{
				ll sum_all = 0;
				for (int _ = 0; _ < (int)col[i].size(); _++) {
					int p = col[i][_].second, x = X[p];
					sum_all += W[p];
					dp[p][3] = max(dp[p][3], dp[x][0] + sum_all);
				}
				if (i && !col[i - 1].empty()) {
					int ptr = (int)col[i].size() - 1;
					ll pf_sum = 0;
					for (int _ = (int)col[i - 1].size() - 1; _ >= 0; _--) {
						while (ptr >= 0 && col[i - 1][_].first < col[i][ptr].first) {
							pf_sum += W[col[i][ptr].second];
							ptr--;
						}
						tmp[_] = pf_sum;
					}
					pf_sum = 0;
					for (int _ = (int)col[i].size() - 1; _ >= 0; _--) {
						tmp2[_] = pf_sum;
						pf_sum += W[col[i][_].second];
					}
					ptr = 0;
					ll rs = -(ll)1e16;
					for (int _ = 0; _ < (int)col[i].size(); _++) {
						while (ptr < (int)col[i - 1].size() && col[i - 1][ptr].first < col[i][_].first) {
							rs = max(rs, dp[col[i - 1][ptr].second][3] + tmp[ptr]);
							ptr++;
						}
						dp[col[i][_].second][3] = max(dp[col[i][_].second][3], rs - tmp2[_]);
					}
				}
			}
		}
	}
	return dp[N][0];
}

• 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