제출 #692919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
692919		Pyqe	메기 농장 (IOI22_fish)	C++17	52 / 100	1097 ms	236192 KiB

fish

#include <bits/stdc++.h>
#include "fish.h"

using namespace std;

const long long inf=1e18;
long long aa[3069][3069],dp[3069][3069][2];
pair<pair<long long,long long>,long long> a[300069];

long long max_weights(int n,int m,vector<int> xa,vector<int> ya,vector<int> wg)
{
	long long i,j,x,y,w,mx,z=-inf;
	
	for(i=1;i<=m;i++)
	{
		x=xa[i-1]+1;
		y=ya[i-1]+1;
		w=wg[i-1];
		a[i]={{x,y},w};
		aa[x][y]=w;
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			dp[i][j][0]=dp[i-1][j][0];
		}
		mx=-inf;
		for(j=n;j;j--)
		{
			mx=max(mx,dp[i-1][j][1]);
			if(i>1)
			{
				mx=max(mx,dp[i-2][j][0]);
			}
			dp[i][j][0]=max(dp[i][j][0],mx+aa[i][j]);
		}
		mx=-inf;
		for(j=1;j<=n;j++)
		{
			dp[i][j][0]=max(dp[i][j][0],mx+aa[i][j]);
			mx=max(mx,dp[i][j][0]);
		}
		if(i==1)
		{
			for(j=1;j<=n;j++)
			{
				dp[i][j][1]=-inf;
			}
		}
		else
		{
			for(j=1;j<=n;j++)
			{
				dp[i][j][1]=dp[i-1][j][1];
			}
			mx=-inf;
			for(j=1;j<=n;j++)
			{
				mx=max(mx,dp[i-2][j][0]);
				dp[i][j][1]=max(dp[i][j][1],mx+aa[i][j]);
			}
			mx=-inf;
			for(j=n;j;j--)
			{
				dp[i][j][1]=max(dp[i][j][1],mx+aa[i][j]);
				mx=max(mx,dp[i][j][1]);
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		z=max(z,max(dp[n][i][1],dp[n-1][i][0]));
	}
	return z;
}

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