Submission #626862

#	Time	Username	Problem	Language	Result	Execution time	Memory
626862		Noam527	Catfish Farm (IOI22_fish)	C++17	100 / 100	152 ms	27696 KiB

fish

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

const int N = 100005;
vector<pair<int, int>> Y[N];
int c[N];
vector<ll> D[N], F[N];
ll E[N];

ll max_weights(int n, int m, vector<int> x, vector<int> y,
                      vector<int> w) {
	for (int i = 0; i < m; i++)
		Y[x[i]].emplace_back(y[i], w[i]);
	for (int i = 0; i < n; i++)
		sort(Y[i].begin(), Y[i].end()), c[i] = Y[i].size();

	// initialize column 0:
	E[0] = 0;
	F[0].resize(c[0], -(ll)1e18);
	D[0].resize(c[0]);
	if (c[0]) {
		D[0][0] = Y[0][0].second;
		for (int j = 1; j < c[0]; j++) {
			D[0][j] = D[0][j - 1] + Y[0][j].second;
		}
	}
	// begin dp:
	for (int i = 1; i < n; i++) {
		//cout << "begin " << i << '\n';
		E[i] = E[i - 1];
		for (int j = 0; j < c[i - 1]; j++)
			E[i] = max(max(E[i], D[i - 1][j]), F[i - 1][j]);
		//cout << "E[i] " << E[i] << '\n';
		if (!c[i]) continue;

		D[i].resize(c[i]);
		F[i].resize(c[i]);

		vector<ll> below(c[i]), above(c[i]);
		// compute below
		int z = 0;
		ll bestfound = -(ll)1e18;
		for (int k = 0; k < c[i]; k++) {
			while (z < c[i - 1] && Y[i - 1][z].first < Y[i][k].first) {
				bestfound = max(bestfound, D[i - 1][z]);
				z++;
			}
			below[k] = bestfound;
		}
		// compute above
		z = c[i - 1] - 1;
		bestfound = -(ll)1e18;
		for (int k = c[i] - 1; k >= 0; k--) {
			while (z >= 0 && Y[i - 1][z].first > Y[i][k].first) {
				bestfound = max(bestfound, F[i - 1][z]);
				z--;
			}
			above[k] = bestfound;
		}
		// compute D:
		ll bestF = -(ll)1e18;
		if (c[i - 1])
			bestF = *max_element(F[i - 1].begin(), F[i - 1].end());
		D[i][0] = max(max(below[0], E[i - 1]), bestF) + Y[i][0].second;
		for (int j = 1; j < c[i]; j++) {
			D[i][j] = max(below[j], D[i][j - 1]) + Y[i][j].second;
		}
		// compute F:
		F[i][c[i] - 1] = max(E[i - 1], above[c[i] - 1]) + Y[i][c[i] - 1].second;
		for (int j = c[i] - 2; j >= 0; j--) {
			F[i][j] = max(above[j], F[i][j + 1]) + Y[i][j].second;
		}
		/*
		for (int j = 0; j < c[i]; j++) {
			cout << "D[i][" << j << "] " << D[i][j] << '\n';
		}
		for (int j = 0; j < c[i]; j++) {
			cout << "F[i][" << j << "] " << F[i][j] << '\n';
		}
		*/
	}
	ll result = E[n - 1];
	for (int j = 0; j < c[n - 1]; j++) {
		result = max(result, F[n - 1][j]);
	}
	return result;
}

• 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