Submission #1005235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005235		alex_2008	Catfish Farm (IOI22_fish)	C++17	53 / 100	399 ms	894032 KiB

fish

//#include "fish.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 3e2 + 10;
const int M = 4e5 + 10;
ll col_sm[MAX_N][MAX_N];
ll dp[MAX_N][MAX_N][MAX_N];
ll dp_pref[MAX_N][MAX_N][MAX_N];
ll dp_suff[MAX_N][MAX_N][MAX_N];
ll pref_mx[MAX_N][MAX_N][MAX_N];
ll dpp[MAX_N][MAX_N][MAX_N];
ll esim[M][2][2];
ll f(int r, int c) {
	if (r == -1) return 0;
	return col_sm[r][c];
}
ll sm(int c, int r1, int r2) {
	return f(c, r2) - f(c, r1 - 1);
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	if (N <= 300) {
		for (int i = 0; i < M; i++) {
			col_sm[X[i]][Y[i]] = W[i];
		}
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= N; j++) {
				col_sm[i][j] += col_sm[i][j - 1];
			}
		}
		for (int h1 = 0; h1 <= N; h1++) {
			for (int h2 = 0; h2 <= N; h2++) {
				if (h1 >= h2) dp[1][h1][h2] = sm(1, h2, h1 - 1);
				else dp[1][h1][h2] = sm(0, h1, h2 - 1);

			}
		}
		for (int h1 = 0; h1 <= N; h1++) {
			for (int h2 = 0; h2 <= N; h2++) {
				pref_mx[1][h1][h2] = max(dp[1][h1][h2], pref_mx[1][h1 - 1][h2]);
				if (h1 >= h2) {
					dp_pref[1][h1][h2] = max(dp_pref[1][h1 - 1][h2], dp[1][h1][h2] - sm(1, h2, h1 - 1));
				}
			}
		}
		for (int h1 = N; h1 >= 0; h1--) {
			for (int h2 = 0; h2 <= h1; h2++) {
				dp_suff[1][h1][h2] = max(dp[1][h1][h2], dp_suff[1][h1 + 1][h2]);
			}
		}
		for (int i = 2; i < N; i++) {
			for (int h1 = 0; h1 <= N; h1++) {
				for (int h2 = 0; h2 <= N; h2++) {
					if (h1 >= h2) {
						dp[i][h1][h2] = pref_mx[i - 1][N][h1] + sm(i, h2, h1 - 1);
					}
					else {
						dp[i][h1][h2] = pref_mx[i - 1][h1][h1] + sm(i - 1, h1, h2 - 1);
						dp[i][h1][h2] = max(dp[i][h1][h2], dp_suff[i - 1][h2][h1]);
						dp[i][h1][h2] = max(dp[i][h1][h2], dp_pref[i - 1][h2][h1] + sm(i - 1, h1, h2 - 1));
					}
				}
			}
			for (int h1 = 0; h1 <= N; h1++) {
				for (int h2 = 0; h2 <= N; h2++) {
					pref_mx[i][h1][h2] = max(dp[i][h1][h2], pref_mx[i][h1 - 1][h2]);
					if (h1 >= h2) {
						dp_pref[i][h1][h2] = max(dp_pref[i][h1 - 1][h2], dp[i][h1][h2] - sm(i, h2, h1 - 1));
					}
				}
			}
			for (int h1 = N; h1 >= 0; h1--) {
				for (int h2 = 0; h2 <= h1; h2++) {
					dp_suff[i][h1][h2] = max(dp[i][h1][h2], dp_suff[i][h1 + 1][h2]);
				}
			}
		}
		ll mx = 0;
		for (int h1 = 0; h1 <= N; h1++) {
			for (int h2 = 0; h2 <= N; h2++) {
				mx = max(mx, dp[N - 1][h1][h2]);
			}
		}
		return mx;
	}
	bool ch = true;
	ll sm = 0;
	for (int i = 0; i < M; i++) {
		if (X[i] % 2 == 1) {
			ch = false;
		}
		sm += W[i];
	}
	if (ch) return sm;
	bool ch2 = true;
	for (int i = 0; i < M; i++) {
		if (X[i] > 1) ch2 = false;
	}
	if (ch2) {
		bool ch0 = false, ch1 = false;
		for (int i = 0; i < M; i++) {
			if (X[i] == 0) ch0 = true;
			else ch1 = true;
		}
		if (!ch1 || !ch0) return sm;
		sm = 0;
		map <pair<int, int>, int> mp;
		for (int i = 0; i < M; i++) {
			mp[{ X[i], Y[i] }] = W[i];
			if (X[i] == 1) sm += W[i];
		}
		ll ans = sm;
		for (int i = 0; i < N; i++) {
			sm -= mp[{ 1, i }];
			sm += mp[{ 0, i }];
			ans = max(ans, sm);
		}
		return ans;
	}
	map <pair<int, int>, int> mp;
	for (int i = 0; i < M; i++) {
		mp[{ X[i], Y[i] }] = W[i];
	}
	esim[1][0][0] = 0;
	esim[1][0][1] = mp[{ 0, 0 }];
	esim[1][1][0] = mp[{ 1, 0 }];
	esim[1][1][1] = 0;
	for (int i = 2; i < N; i++) {
		esim[i][0][0] = max(esim[i - 1][1][0], esim[i - 1][0][0]);
		esim[i][1][1] = max(esim[i - 1][1][1], esim[i - 1][0][1]);
		esim[i][0][1] = max(esim[i - 1][1][0], esim[i - 1][0][0] + mp[{ i - 1, 0 }]);
		esim[i][1][0] = max(esim[i - 1][0][1], esim[i - 1][1][1]) + mp[{ i, 0 }];
	}
	return max({ esim[N - 1][0][0], esim[N - 1][0][1],
		esim[N - 1][1][0], esim[N - 1][1][1] });
}
/*
int main() {
	//3 2
	//0 0 1
	//1 1 1
	//cout << max_weights(3, 2, { 0, 1 }, { 0, 1 }, { 1, 1 });
	
}
*/

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