Submission #1189392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189392		mertbbm	Catfish Farm (IOI22_fish)	C++20	0 / 100	26 ms	6472 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());

int arr[305][305];
int n;
int memo[305][305][2];

int dp(int index, int h, bool amos){
	if(index==n) return 0;
	if(memo[index][h][amos]!=-1) return memo[index][h][amos];
	int ans=-1e15;
	if(!amos){
		//go up
		int add=0;
		for(int x=h;x<=n;x++){
			ans=max(ans,dp(index+1,x,0)+add);
			add+=arr[index][x];
		}
		if(h==n){
			ans=max(ans,dp(index,h,1));
			if(index+1!=n){
				int add2=0;
				for(int y=1;y<=n;y++) add2+=arr[index+1][y];
				ans=max(ans,dp(index+2,h,1)+add2);
			}
		}
	}
	else{
		//go down
		if(h==0) ans=max(ans,dp(index+1,h,0));
		int add=0;
		for(int x=h;x>=1;x--){
			ans=max(ans,dp(index+1,x,1)+add);
			add+=arr[index+1][x];
		}
	}
	return memo[index][h][amos]=ans;
}

long long max_weights(int32_t N, int32_t m, vector<int32_t>a, vector<int32_t>b, vector<int32_t>w){
	n=N;
	for(int x=0;x<m;x++){
		a[x]++;
		b[x]++;
		arr[a[x]][b[x]]+=w[x];
	}
	
	memset(memo,-1,sizeof(memo));
	return dp(0,0,0);
}

• 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