Submission #1189444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189444		mertbbm	Catfish Farm (IOI22_fish)	C++20	100 / 100	258 ms	82444 KiB

fish

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

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

long long max_weights(int32_t n, int32_t m, vector<int32_t>a, vector<int32_t>b, vector<int32_t>w){	
	vector<int>dis[n+5];
	
	for(int x=0;x<m;x++){
		a[x]++;
		b[x]++;
		dis[a[x]].push_back(b[x]-1);
		dis[a[x]].push_back(b[x]);
		dis[a[x]-1].push_back(b[x]);
		dis[a[x]+1].push_back(b[x]);
	}
	for(int x=0;x<=n;x++){
		dis[x].push_back(0);
		dis[x].push_back(n);
	}
	
	vector<int>arr[n+5];
	for(int x=0;x<=n;x++){
		sort(dis[x].begin(),dis[x].end());
		dis[x].resize(unique(dis[x].begin(),dis[x].end())-dis[x].begin());
		//show4(dis[x],dis[x]);
		arr[x]=vector<int>(dis[x].size()+5,0);
	}
	
	for(int x=0;x<m;x++){
		int index=lower_bound(dis[a[x]].begin(),dis[a[x]].end(),b[x])-dis[a[x]].begin();
		arr[a[x]][index]+=w[x];
	}
	
	vector<int>dp[2][n+5];
	dp[0][0]=vector<int>(dis[0].size()+5,-1e15);
	dp[1][0]=vector<int>(dis[0].size()+5,-1e15);
	dp[0][0][0]=0;
	for(int index=1;index<=n;index++){
		dp[0][index]=vector<int>(dis[index].size()+5,-1e15);
		dp[1][index]=vector<int>(dis[index].size()+5,-1e15);
		//go up
		int add=-1e15;
		int add2=0;
		int ptr=0;
		int cur=0;
		for(auto h:dis[index]){
			while(ptr<(int)dis[index-1].size()&&dis[index-1][ptr]<=h){
				add=max(add+arr[index-1][ptr],dp[0][index-1][ptr]);
				add2+=arr[index-1][ptr];
				ptr++;
			}
			dp[0][index][cur]=max(dp[0][index][cur],add);
			
			if(h==n){
				dp[1][index][cur]=max(dp[0][index][cur],dp[1][index][cur]);
				if(index>2){
					int target=lower_bound(dis[index-2].begin(),dis[index-2].end(),n)-dis[index-2].begin();
					dp[1][index][cur]=max(dp[1][index][cur],add2+dp[0][index-2][target]);
				}
			}
			cur++;
		}
		
		//go down
		add=-1e15;
		
		ptr=dis[index-1].size()-1;
		for(int y=dis[index].size()-1;y>=0;y--){
			int h=dis[index][y];
			while(ptr>=0&&dis[index-1][ptr]>=h){
				add=max(add,dp[1][index-1][ptr]);
				ptr--;
			}
			dp[1][index][y]=max(dp[1][index][y],add);
			add+=arr[index][y];
		}
		dp[0][index][0]=max(dp[1][index-1][0],dp[0][index][0]);
		
		//show(index,index-1);
		//show4(dis[index],dis[index]);
		//show4(dp0,dp[0][index]);
		//show4(dp1,dp[1][index]);
	}
	
	int maxi=0;
	for(int x=0;x<=n;x++){
		for(auto it:dp[0][x]) maxi=max(maxi,it);
		for(auto it:dp[1][x]) maxi=max(maxi,it);
	}
	return maxi;
}

• 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