Submission #659200

#	Time	Username	Problem	Language	Result	Execution time	Memory
659200		pere_gil	Catfish Farm (IOI22_fish)	C++17	0 / 100	97 ms	46552 KiB

fish

#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
             
typedef long long ll;
#define all(x) x.begin(),x.end()

int get_pos(vector<ll> &fish, ll x){
	int pos=lower_bound(all(fish),x)-fish.begin();
	if(x!=fish[pos]) pos--;
	return pos;
}

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){

	vector<pair<ll,ll>> inf_fish[n];
	for(int i=0;i<m;i++) inf_fish[x[i]].push_back({y[i]+1,w[i]});
	for(int i=0;i<m;i++) sort(all(inf_fish[i]));
	
	vector<ll> pier[n],fish[n],sum[n];
	for(int i=0;i<n;i++){
		pier[i].push_back(0);
		fish[i].push_back(0);
		sum[i].push_back(0);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<(int)inf_fish[i].size();j++){
			fish[i].push_back(inf_fish[i][j].first);
			sum[i].push_back(inf_fish[i][j].second);
			if(i) pier[i-1].push_back(inf_fish[i][j].first);
			if(i!=n-1) pier[i+1].push_back(inf_fish[i][j].first);
		}
	}
	for(int i=0;i<n;i++)
		for(int j=1;j<(int)sum[i].size();j++)
			sum[i][j]+=sum[i][j-1];
	
	vector<vector<vector<ll>>> dp[n];
	for(int i=0;i<n;i++){
		int j=(i>=2) ? pier[i-2].size() : 1;
		int k=(i) ? pier[i-1].size() : 1;
		int l=pier[i].size();
		dp[i].assign(j,vector<vector<ll>>(k,vector<ll>(l,0)));
	}

	for(int i=0;i<(int)pier[0].size();i++)
		for(int j=0;j<(int)pier[1].size();j++){
			if(pier[0][i]>=pier[1][j]){
				int pos_up=get_pos(fish[1],pier[0][i]);
				int pos_down=get_pos(fish[1],pier[1][j]);
				dp[1][0][i][j]+=sum[1][pos_up]-sum[1][pos_down];
			}
			else{
				int pos_up=get_pos(fish[0],pier[1][i]);
				int pos_down=get_pos(fish[0],pier[0][j]);
				dp[1][0][i][j]+=sum[0][pos_up]-sum[0][pos_down];
			}
		}

	if(n<3){
		ll res=0;
		for(int i=0;i<(int)pier[0].size();i++)
			for(int j=0;j<(int)pier[1].size();j++)
				res=max(res,dp[1][0][i][j]);
		return res;
	}

	for(int i=2;i<n;i++){
		for(int j=0;j<(int)pier[i-2].size();j++){
			for(int k=0;k<(int)pier[i-1].size();k++){

				ll prev=0;
				if(i>=3)
					for(int l=0;l<(int)pier[i-3].size();l++)
						prev=max(prev,dp[i-1][l][j][k]);
				else
					prev=dp[1][0][j][k];
				
				for(int l=0;l<(int)pier[i].size();l++){
					dp[i][j][k][l]+=prev;

					/*
					printf("%d: %lld\n",i-2,pier[i-2][j]);
					printf("%d: %lld\n",i-1,pier[i-1][k]);
					printf("%d: %lld\n",i,pier[i][l]);
					printf("prev: %lld at %d\n",prev,pos);
					*/
					
					if(pier[i-1][k]>=pier[i][l]){
						int pos_up=get_pos(fish[i],pier[i-1][k]);
						int pos_down=get_pos(fish[i],pier[i][l]);

						/*
						ll act=sum[i][pos_up]-sum[i][pos_down];
						printf("pos_up: %d -> %lld\n",pos_up,fish[i][pos_up]);
						printf("pos_down: %d -> %lld\n",pos_down,fish[i][pos_down]);
						printf("%lld - %lld -> %lld\n",sum[i][pos_up],sum[i][pos_down],act);
						*/
						
						dp[i][j][k][l]+=sum[i][pos_up]-sum[i][pos_down];
					}
					if(pier[i][l]>pier[i-1][k] && pier[i][l]>=pier[i-2][j]){
						int pos_up=get_pos(fish[i-1],pier[i][l]);
						int pos_down=get_pos(fish[i-1],max(pier[i-1][k],pier[i-2][j]));

						/*
						ll act=sum[i-1][pos_up]-sum[i-1][pos_down];
						printf("pos_up: %d -> %lld\n",pos_up,fish[i-1][pos_up]);
						printf("pos_down: %d -> %lld\n",pos_down,fish[i-1][pos_down]);
						printf("%lld - %lld -> %lld\n",sum[i-1][pos_up],sum[i-1][pos_down],act);
						*/
						
						dp[i][j][k][l]+=sum[i-1][pos_up]-sum[i-1][pos_down];
					}
					//printf("%lld\n\n",dp[i][j][k][l]);
				}
			}
		}
	}
	
	ll res=0;
	for(int i=0;i<(int)pier[n-3].size();i++)
		for(int j=0;j<(int)pier[n-2].size();j++)
			for(int k=0;k<(int)pier[n-1].size();k++)
				res=max(res,dp[n-1][i][j][k]);
	
	return res;
}

• 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