Submission #1210751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210751		Nicolaikrob	Catfish Farm (IOI22_fish)	C++17	52 / 100	962 ms	2162688 KiB

fish

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

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
	int sz = n+3;
	vector<vector<ll>> G(sz, vector<ll> (sz, 0)), PS(sz, vector<ll> (sz, 0));
	for(int i = 0; i < m; i++) G[X[i]][Y[i]] = W[i];
	for(int c = 0; c < n; c++) {
		for(int r = 1; r <= n; r++)
			PS[c][r] = PS[c][r-1]+G[c][r-1];
	}
	vector<vector<ll>> higher(sz, vector<ll> (sz, 0)), best(sz, vector<ll> (sz, 0));
	vector<ll> apple(sz, 0), dp(sz, 0);
	vector<vector<ll>> banana(sz, vector<ll> (sz, 0));
	apple[0] = n;
	for(int i = 0; i <= n; i++) higher[1][i] = PS[0][i];
	for(int i = 0; i <= n; i++) best[1][i] = max(higher[1][i], PS[1][n]-PS[1][i]);
	for(int i = 0; i <= n; i++) dp[1] = max(dp[1], best[1][i]);
	for(int i = 0; i <= n; i++) {
		if(best[1][apple[1]]+PS[1+1][apple[1]] < best[1][i]+PS[1+1][i])
			apple[1] = i;
	}
	for(int i = 0; i <= n; i++)
		banana[1][i] = max(banana[1][max(i-1, 0)], higher[1][i]-PS[1][i]);
	for(int c = 2; c < n; c++) {
		for(int r = 0; r <= n; r++) {
			// max row2back_comb, row2back+PS1back_r
			higher[c][r] = max(best[c-2][apple[c-2]]+PS[c-1][apple[c-2]], dp[c-2]+PS[c-1][r]);

			// max bounded row1back_-PS1back  + PS1back_r		(not sus without bound right?)
			higher[c][r] = max(higher[c][r], banana[c-1][r]+PS[c-1][r]);
			
			// max row1back_+PS0back - PS0back_r
			best[c][r] = max(higher[c][r], best[c-1][apple[c-1]]+PS[c][apple[c-1]]-PS[c][r]);
		}

		for(int i = 0; i <= n; i++)
			dp[c] = max(dp[c], best[c][i]);
		for(int i = 0; i <= n; i++) {
			if(best[c][apple[c]]+PS[c+1][apple[c]] < best[c][i]+PS[c+1][i])
				apple[c] = i;
		}
		for(int i = 1; i <= n; i++)
			banana[c][i] = max(banana[c][max(i-1, 0)], higher[c][i]-PS[c][i]);
	}
	// for(auto x : dp) cout << x << ' ';
	// cout << endl;
	// for(auto x : banana[1]) cout << x << ' ';
	// cout << endl;
	return dp[n-1];
}

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