QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#329122#7988. 史莱姆工厂C1942huangjiaxuWA 5ms6104kbC++141.3kb2024-02-16 13:49:142024-02-16 13:49:15

Judging History

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

  • [2024-02-16 13:49:15]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:6104kb
  • [2024-02-16 13:49:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=155;
int n,m,w,a[N],b[N],p[25],dp[N][N],fl[N][N][11],fr[N][N][11];
inline void U(int &x,int y){
	if(x<y)x=y;
}
int main(){
	scanf("%d%d%d",&n,&m,&w);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)scanf("%d",&b[i]);
	for(int i=m;i<=2*m-2;++i)scanf("%d",&p[i]);
	for(int i=1;i<m;++i)p[i]=p[m]-(m-i)*w;
	memset(dp,-0x3f,sizeof(dp));
	memset(fl,-0x3f,sizeof(fl));
	memset(fr,-0x3f,sizeof(fr));
	for(int i=1;i<=n;++i)dp[i][i]=p[b[i]],dp[i][i-1]=0;
	for(int l=n-1;l;--l)for(int r=l+1;r<=n;++r){
		if(a[l-1]!=a[r]){
			U(fr[l][r][a[r]],dp[l][r-1]);
			for(int k=l;k<r;++k)if(a[k]==a[r])for(int i=1;i+b[k]<m;++i)U(fr[l][r][i+b[k]],fr[k+1][r][i]+dp[l][k-1]);
		}
		if(a[l]!=a[r+1]){
			U(fl[l][r][a[l]],dp[l+1][r]);
			for(int k=r;k>l;--k)if(a[k]==a[l])for(int i=1;i+b[k]<m;++i)U(fl[l][r][i+b[k]],fl[l][k-1][i]+dp[k+1][r]);
		}
		for(int k=l;k<r;++k)if(a[k]!=a[r+1]||a[k+1]!=a[l-1])U(dp[l][r],dp[l][k]+dp[k+1][r]);
		if(a[l]!=a[r])continue;
		U(dp[l][r],dp[l+1][r-1]+p[b[l]+b[r]]);
		for(int k=l+1;k<r;++k)if(a[k]==a[l])
			for(int i=1;i<m;++i)for(int j=1;j<m;++j)if(i+b[k]<m||j+b[k]<m){
				U(dp[l][r],fl[l][k-1][i]+fr[k+1][r][j]+p[i+j+b[k]]);
				U(dp[l][r],fl[l][k-1][j]+fr[k+1][r][i]+p[i+j+b[k]]);
			}
	}
	printf("%d\n",dp[1][n]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 6012kb

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: 5ms
memory: 5944kb

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: 5ms
memory: 6104kb

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:

9258790

result:

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