QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#396342#7988. 史莱姆工厂zyxawaWA 8ms11592kbC++141.9kb2024-04-22 17:39:402024-04-22 17:39:42

Judging History

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

  • [2024-04-22 17:39:42]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:11592kb
  • [2024-04-22 17:39:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,s,w,c[151],m[151],p[21];
ll f[151][151],fl[151][151][21],fr[151][151][21];
void upd(ll &x,ll y){x=max(x,y);}
int main(){
	memset(f,-0x3f,sizeof(f)),memset(fl,-0x3f,sizeof(fl)),memset(fr,-0x3f,sizeof(fr));
	scanf("%d%d%d",&n,&s,&w);
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	for(int i=1;i<=n;i++) scanf("%d",&m[i]);
	for(int i=s;i<=2*s-2;i++) scanf("%d",&p[i]);
	for(int i=1;i<s;i++) p[i]=p[s]-(s-i)*w;
	for(int i=1;i<=n;i++) f[i][i]=p[m[i]],fl[i][i][m[i]]=fr[i][i][m[i]]=f[i][i-1]=0;
	for(int t=2;t<=n;t++){
		for(int l=1;l+t-1<=n;l++){
			int r=l+t-1;
			//upd(fl[l][r][m[l]],f[l+1][r]);
			//for(int k=l+1;k<r;k++) if(c[k]==c[l]) for(int i=1;i<s-m[k];i++) upd(fl[l][r][i+m[k]],fl[l][k-1][i]+f[k+1][r]);
			//upd(fr[l][r][m[r]],f[l][r-1]);
			//for(int k=l+1;k<r;k++) if(c[k]==c[r]) for(int i=1;i<s-m[k];i++) upd(fr[l][r][i+m[k]],fr[k+1][r][i]+f[l][k-1]);

			upd(fl[l][r][m[l]],f[l+1][r]);
			for(int k=l-1;k<r;k++) if(c[k+1]==c[l]) for(int i=1;i+m[l]<s;i++) upd(fl[l][r][i+m[l]],f[l][k]+fl[k+1][r][i]);
			upd(fr[l][r][m[l]],f[l][r-1]);
			for(int k=l;k<=r;k++) if(c[k]==c[r]) for(int i=1;i+m[r]<s;i++) upd(fr[l][r][i+m[r]],f[k+1][r]+fr[l][k][i]);
			for(int k=l;k<r;k++) if(c[k]!=c[r+1]||c[k+1]!=c[l-1]) upd(f[l][r],f[l][k]+f[k+1][r]);
			if(c[l]!=c[r]) continue;
			upd(f[l][r],f[l+1][r-1]+p[m[l]+m[r]]);

			// for(int k=l+1;k<r;k++){
			// 	if(c[k]==c[l]){
			// 		for(int i=1;i<s;i++){
			// 			for(int j=1;j<s;j++){
			// 				if(i+m[k]<s||j+m[k]<s) upd(f[l][r],fl[l][k-1][i]+fr[k+1][r][j]+p[i+j+m[k]]);
			// 			}
			// 		}
			// 	}
			// }
			for(int k=l;k<r;k++){
				for(int i=1;i<s;i++){
					for(int j=1;j<s;j++){
						upd(f[l][r],fl[l][k][i]+fr[k+1][r][j]+p[i+j]);
					}
				}
			}
		}
	}
	printf("%lld",f[1][n]);
	return 0;
}
//dp[l][r][k][c]区间[l,r]剩下一个重量k,颜色为c的最大值

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 11592kb

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

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: -100
Wrong Answer
time: 8ms
memory: 11572kb

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:

17635677334

result:

wrong answer 1st lines differ - expected: '392867316', found: '17635677334'