Submission #775800

#	Time	Username	Problem	Language	Result	Execution time	Memory
775800		SanguineChameleon	Catfish Farm (IOI22_fish)	C++17	12 / 100	136 ms	38372 KiB

fish

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

const int maxN = 1e5 + 20;
const long long inf = 1e18L + 20;
vector<pair<int, int>> col[maxN];
vector<long long> dp_down[maxN];
vector<long long> dp_up[maxN];

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	for (int i = 0; i < M; i++) {
		col[X[i]].emplace_back(Y[i], W[i]);
	}
	for (int i = 0; i < N; i++) {
		col[i].emplace_back(-1, 0);
		col[i].emplace_back(N, 0);
		sort(col[i].begin(), col[i].end());
		dp_down[i].resize(col[i].size(), (i ? -inf : 0));
		dp_up[i].resize(col[i].size(), (i ? -inf: 0));
	}
	for (int i = 1; i < N; i++) {
		int prv_sz = col[i - 1].size();
		int cur_sz = col[i].size();
		int pt = cur_sz - 1;
		for (int j = prv_sz - 1; j >= 0; j--) {
			while (col[i][pt].first > col[i - 1][j].first) {
				pt--;
			}
			dp_down[i][pt] = max(dp_down[i][pt], max(dp_up[i - 1][j], dp_down[i - 1][j]) + (col[i][pt].first < col[i - 1][j].first ? col[i][pt].second : 0));
		}
		for (int j = cur_sz - 2; j >= 0; j--) {
			dp_down[i][j] = max(dp_down[i][j], dp_down[i][j + 1] + col[i][j].second);
		}
		long long max_up = -inf;
		long long max_down = -inf;
		pt = -1;
		for (int j = 0; j < cur_sz; j++) {
			while (pt + 1 < prv_sz && col[i - 1][pt + 1].first < col[i][j].first) {
				max_up = max(dp_up[i - 1][pt + 1], max_up + col[i - 1][pt + 1].second);
				max_down = max(max_down, dp_down[i - 1][pt + 1]);
				pt++;
			}
			if (pt + 1 < prv_sz && col[i - 1][pt + 1].first == col[i][j].first) {
				dp_up[i][j] = max(dp_up[i][j], dp_up[i - 1][pt + 1]);
				dp_up[i][j] = max(dp_up[i][j], dp_down[i - 1][pt + 1]);
			}
			dp_up[i][j] = max(dp_up[i][j], max_up);
			dp_up[i][j] = max(dp_up[i][j], max_down);
		}
	}
	long long res = 0;
	for (int i = 0; i < (int)col[N - 1].size(); i++) {
		res = max(res, dp_up[N - 1][i]);
		res = max(res, dp_down[N - 1][i]);
	}
	return res;
}

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