Submission #1234507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234507		PlayVoltz	Catfish Farm (IOI22_fish)	C++20	100 / 100	362 ms	126120 KiB

fish

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

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int max_weights(signed n, signed m, vector<signed> x, vector<signed> y, vector<signed> w){
	vector<vector<pii> > vect(n);
	vector<vector<vector<int> > > dp(n), down(n);
	vector<vector<int> > l(n), up(n);
	for (int i=0; i<m; ++i)vect[x[i]].pb(mp(y[i]+1, w[i]));
	for (int i=0; i<n; ++i){
		vect[i].pb(mp(0, 0));
		sort(vect[i].begin(), vect[i].end());
		for (int j=1; j<vect[i].size(); ++j)vect[i][j].se+=vect[i][j-1].se;
	}
	for (int i=0; i<n; ++i){
		l[i].pb(0);
		if (i)for (auto a:vect[i-1])l[i].pb(a.fi);
		if (i!=n-1)for (auto a:vect[i+1])l[i].pb(a.fi);
		sort(l[i].begin(), l[i].end());
		l[i].erase(unique(l[i].begin(), l[i].end()), l[i].end());
		dp[i].resize(l[i].size(), vector<int>(2, 0));
		down[i].resize(l[i].size(), vector<int>(2, 0));
		up[i].resize(l[i].size(), 0);
	}
	int i=0;
	for (int j=l[i].size()-1; j>=0; --j)up[i][j]=max((j!=l[i].size()-1?up[i][j+1]:0), max(dp[i][j][0], dp[i][j][1])+(upper_bound(vect[i+1].begin(), vect[i+1].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
	for (int j=0; j<l[i].size(); ++j)down[i][j][0]=max((j?down[i][j-1][0]:0), dp[i][j][0]-(upper_bound(vect[i].begin(), vect[i].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
	for (int j=0; j<l[i].size(); ++j)down[i][j][1]=max((j?down[i][j-1][1]:0), dp[i][j][1]-(upper_bound(vect[i].begin(), vect[i].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
	for (int i=1; i<n; ++i){
		for (int j=0; j<l[i].size(); ++j){
			int id=upper_bound(l[i-1].begin(), l[i-1].end(), l[i][j])-l[i-1].begin()-1;
			dp[i][j][0]=max(down[i-1][id][0]+(upper_bound(vect[i-1].begin(), vect[i-1].end(), mp(l[i][j], LLONG_MAX/2))-1)->se, down[i-1][id][1]);
			dp[i][j][1]=up[i-1][id]-(upper_bound(vect[i].begin(), vect[i].end(), mp(l[i][j], LLONG_MAX/2))-1)->se;
		}
		if (i==n-1)continue;
		for (int j=l[i].size()-1; j>=0; --j)up[i][j]=max((j!=l[i].size()-1?up[i][j+1]:0), max(dp[i][j][0], dp[i][j][1])+(upper_bound(vect[i+1].begin(), vect[i+1].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
		for (int j=0; j<l[i].size(); ++j)down[i][j][0]=max((j?down[i][j-1][0]:0), dp[i][j][0]-(upper_bound(vect[i].begin(), vect[i].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
		for (int j=0; j<l[i].size(); ++j)down[i][j][1]=max((j?down[i][j-1][1]:0), dp[i][j][1]-(upper_bound(vect[i].begin(), vect[i].end(), mp(l[i][j], LLONG_MAX/2))-1)->se);
	}
	int ans=0;
	for (auto a:dp[n-1])ans=max({ans, a[0], a[1]});
	return ans;
}

• 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