Submission #1231853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231853		ssafarov	Catfish Farm (IOI22_fish)	C++20	17 / 100	48 ms	7240 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define en '\n'
#define all(a) a.begin() , a.end()
#define fi first
#define se second

using namespace std;

ll dp[301][10][10][10];
ll ps[301][10];

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
	ll tmx = 0;
	bool ok = 1;
	for(ll i = 0; i < m; ++i){
		x[i]++;
		y[i]++;
	}
	for(ll i = 0; i < m; ++i){
		tmx = max(tmx, (ll)x[i]);
		if(x[i] % 2 == 0) ok = 0;
	}
	if(ok){
		ll ans = 0;
		for(ll i = 0; i < m; ++i){
			ans += w[i];
		}
		return ans;
	}
	if(n == 2){
		ll ans1 = 0;
		ll ans2 = 0;
		for(ll i = 0; i < m; ++i){
			if(x[i] == 1) ans1 += w[i];
			else ans2 += w[i];
		}
		return max(ans1, ans2);
	}
	n = min(n, (int)tmx + 1);
	ll tmy = 0;
	for(ll i = 0; i < m; ++i){
		tmy = max(tmy, (ll)y[i]);
	}
	if(tmy <= 9){
		for(ll i = 0; i < m; ++i){
			ps[x[i]][y[i]] += w[i];
		}
		for(ll i = 1; i <= n; ++i){
			for(ll j = 1; j <= 9; ++j) ps[i][j] += ps[i][j - 1];
		}
		for(ll i = 0; i <= 9;++i){
			for(ll j = 0; j <= 9; ++j){
				for(ll z = 0; z <= 9; ++z){
					dp[3][i][j][z] = max(0ll, ps[1][j] - ps[1][i]) + max(0ll, ps[2][max(i, z)] - ps[2][j]) + max(0ll, ps[3][j] - ps[3][z]);
				}
			}
		}
		for(ll i = 4; i <= n; ++i){
			ll mx[10][10];
			for(ll j = 0; j <= 9; ++j){
				for(ll z = 0; z <= 9; ++z) mx[j][z] = 0;
			}
			for(ll j = 0; j <= 9; ++j){
				for(ll z = 0; z <= 9; ++z){
					for(ll f = 0; f <= 9; ++f){
						mx[z][f] = max(mx[z][f], dp[i - 1][j][z][f]);
					}
				}
			}
			for(ll j = 0; j <= 9; ++j){
				for(ll z = 0; z <= 9; ++z){
					for(ll f = 0; f <= 9; ++f){
						dp[i][j][z][f] = mx[j][z] + max(0ll, ps[i - 1][f] - ps[i - 1][max(z, j)]) + max(0ll, ps[i][z] - ps[i][f]);
					}
				}
			}
		}
		ll ans = 0;
		for(ll i = 0; i <= 9; ++i){
			for(ll j = 0; j <= 9; ++j){
				for(ll z = 0;z <= 9; ++z){
					ans = max(ans, dp[n][i][j][z]);
				}
			}
		}
		return ans;
	}
}

// int main(){
	// int n, m; cin >> n >> m;
	// vector<int> x(m), y(m), w(m);
	// for(int i = 0; i < m; ++i) cin >> x[i];
	// for(int i = 0; i < m; ++i) cin >> y[i];
	// for(int i = 0; i < m; ++i) cin >> w[i];
	// cout << max_weights(n, m, x, y, w);
// }

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
   91 | }
      | ^

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