QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302589#7988. 史莱姆工厂PhantomThresholdWA 18ms5792kbC++201.7kb2024-01-10 23:51:162024-01-10 23:51:16

Judging History

你现在查看的是最新测评结果

  • [2024-01-10 23:51:16]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:5792kb
  • [2024-01-10 23:51:16]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

inline void up(int &a,const int &b){ if(a<b)a=b; }
const int maxn = 200;
const int maxk = 12;
const int inf  = 1e15;

int n,K,W;
int ci[maxn],mi[maxn];
int pi[maxn];

int f[maxn][maxn][maxk],g[maxn][maxn],fg[maxn][maxn];

signed main()
{
	ios_base::sync_with_stdio(false);
	
	cin>>n>>K>>W;
	for(int i=1;i<=n;i++) cin>>ci[i];
	for(int i=1;i<=n;i++) cin>>mi[i];
	for(int i=K;i<=2*K-2;i++) cin>>pi[i];
	
	for(int i=1;i<=n;i++) 
	{
		for(int k=0;k<=K;k++) f[i][i][k]=-inf;
		f[i][i][mi[i]]=0;
		g[i][i]= pi[K]-W*(K-mi[i]);
		
		g[i][i-1]=0;
		fg[i][i]= -inf;
	}
	for(int L=2;L<=n;L++)
	{
		for(int r=L;r<=n;r++)
		{
			int l= r-L+1;
			
			fg[l][r]=-inf;
			g[l][r]=-inf;
			for(int k=0;k<=K;k++) f[l][r][k]=-inf;
			
			for(int mid=l+1;mid<=r;mid++)
			{
				//f+f
				if(ci[l]==ci[mid])
				{
					for(int x=1;x<K;x++) for(int y=1;y<K;y++) 
					{
						if(x+y>=K)
						{
							if(r==n||ci[mid]!=ci[r+1]) 
							{
								up(g[l][r],f[l][mid-1][x]+f[mid][r][y]+pi[x+y]);
								up(fg[l][r],f[l][mid-1][x]+f[mid][r][y]+pi[x+y]);
							}
						}
						else
						{
							up(f[l][r][x+y],f[l][mid-1][x]+f[mid][r][y]);
						}
					}
				}
				
				//g+g
				if( l==1||ci[l-1]!=ci[mid] )
					up(g[l][r],g[l][mid-1]+g[mid][r]);
			}
			for(int mid=l;mid<=r;mid++)
			{
				//g+f
				if( (l==1||ci[l-1]!=ci[mid]) && (r==n||ci[mid]!=ci[r+1]) )
				{
					for(int y=1;y<K;y++) up(g[l][r],g[l][mid-1]+f[mid][r][y]+pi[K]-W*(K-y));
				}
			}
			//f+g
			up(f[l][r][mi[l]],g[l+1][r]);
		}
	}
	cout<<g[1][n]<<endl;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3492kb

input:

4 5 6
2 1 2 3
3 3 3 4
5 7 9 11

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

5 7 500
2 3 2 3 2
5 6 6 6 4
1000 900 800 400 200 50

output:

1400

result:

ok single line: '1400'

Test #3:

score: 0
Accepted
time: 18ms
memory: 5748kb

input:

150 10 465782
6 1 4 3 2 6 1 3 5 3 4 6 1 2 1 5 1 6 2 1 5 4 6 1 3 2 6 5 4 3 1 6 3 4 1 4 1 6 3 6 1 4 2 4 6 4 3 1 5 6 4 2 1 4 6 2 5 1 3 1 4 6 5 6 3 2 3 4 2 3 6 3 5 2 6 1 5 4 5 2 4 1 4 3 4 1 3 2 6 1 4 5 4 6 2 1 3 1 2 1 3 5 2 3 2 6 5 3 1 4 1 5 1 6 2 5 4 2 4 1 4 2 5 6 4 3 5 1 3 2 5 4 6 4 3 5 3 4 5 3 2 1 4 ...

output:

392867316

result:

ok single line: '392867316'

Test #4:

score: -100
Wrong Answer
time: 10ms
memory: 5792kb

input:

150 10 10105
8 6 8 6 8 3 8 5 8 5 1 5 1 5 6 5 6 5 6 7 6 5 6 1 6 4 6 4 3 4 9 4 1 4 1 4 1 5 1 9 1 4 1 9 1 9 3 9 1 9 5 9 8 9 8 5 8 7 8 4 8 6 8 6 2 6 9 6 4 6 5 6 5 3 5 1 5 4 5 8 5 8 9 8 7 8 6 8 1 8 1 8 1 8 1 6 1 7 1 7 2 7 4 7 6 7 4 7 4 5 4 7 4 7 4 3 4 3 7 3 2 3 8 3 4 3 4 8 4 7 4 9 4 2 4 2 7 2 8 2 7 2 9 2...

output:

9260890

result:

wrong answer 1st lines differ - expected: '9262990', found: '9260890'