QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#329122 | #7988. 史莱姆工厂 | C1942huangjiaxu | WA | 5ms | 6104kb | C++14 | 1.3kb | 2024-02-16 13:49:14 | 2024-02-16 13:49:15 |
Judging History
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'