Submission #1055932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055932		pawned	Catfish Farm (IOI22_fish)	C++17	0 / 100	663 ms	2097152 KiB

fish

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "fish.h"

int MAX_R = 10;
int MAX_C = 10;

ll max_weights(int N, int M, vector<int> X_g, vector<int> Y_g, vector<int> W_g) {
	MAX_R = N;
	MAX_C = min(N, 10);
	vector<vi> a(N, vi(N, 0));
	for (int i = 0; i < M; i++) {
		a[X_g[i]][Y_g[i]] += W_g[i];
	}
/*	cout<<"a: "<<endl;
	for (vi v : a) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	vector<vi> pfs(MAX_R, vi(MAX_C + 1, 0));	// vertical pfs
	for (int i = 0; i < MAX_R; i++) {
		pfs[i][0] = 0;
		for (int j = 1; j <= MAX_C; j++) {
			pfs[i][j] = pfs[i][j - 1] + a[i][j - 1];
		}
	}
/*	cout<<"pfs: "<<endl;
	for (vi v : pfs) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	vector<vi> dp(MAX_R + 1, vi(MAX_C + 1, 0));
	// dp[i][j]: max sum till i, exclusive; j = pier height
	// prefix max / sum to optimize?
	for (int i = 1; i <= MAX_C; i++) {
		dp[0][i] = -1e18;
	}
	for (int i = 1; i <= MAX_R; i++) {
		// a[i - 1] is empty
		for (int j = 0; j <= MAX_C; j++) {
			dp[i][0] = max(dp[i][0], dp[i - 1][j] + (pfs[i - 1][j] - pfs[i - 1][0]));
		}
		for (int j = 1; j <= MAX_C; j++) {	// fill up to j
			// try all right filled combinations
			if (i == 1) {	// first coln
				dp[i][j] = 0;
			}
			else if (i == 2) {
				for (int k = 0; k <= j; k++) {	// left is up to k <= j
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + (pfs[i - 2][j] - pfs[i - 2][k]));
				}
				for (int k = j + 1; k <= MAX_C; k++) {	// left is up to k > j
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + (pfs[i - 1][k] - pfs[i - 1][j]));
				}
			}
			else {	// i >= 3
				for (int k = 0; k <= j; k++) {	// left is up to k <= j
					for (int l = 0; l <= MAX_C; l++) {	// 2x left is up to l
						if (l >= j) {	// nothing added
							dp[i][j] = max(dp[i][j], dp[i - 2][l] + (pfs[i - 2][l] - pfs[i - 2][k]));
						}
						else if (l >= k) {
							dp[i][j] = max(dp[i][j], dp[i - 2][l] + (pfs[i - 2][j] - pfs[i - 2][k]));
						}
						else {
							dp[i][j] = max(dp[i][j], dp[i - 2][l] + (pfs[i - 3][k] - pfs[i - 3][l]) + (pfs[i - 2][j] - pfs[i - 2][k]));
						}
					}
				}
				for (int k = j + 1; k <= MAX_C; k++) {	// left is up to k > j
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + (pfs[i - 1][k] - pfs[i - 1][j]));
				}
			}
		}
	}
/*	cout<<"dp: "<<endl;
	for (vi v : dp) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	ll ans = 0;
	for (int i = 0; i <= MAX_C; i++) {
		ans = max(ans, dp[MAX_R][i]);
	}
	return ans;
}

// can extend subtask 3 logic for polynomial soln
// optimize with segtree range max if needed

// if have poly soln, can get subtasks 2 and 4 right away by changing bounds

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