QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#396663 | #7988. 史莱姆工厂 | zyxawa | WA | 8ms | 11560kb | C++14 | 1.2kb | 2024-04-22 23:25:02 | 2024-04-22 23:25:03 |
Judging History
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),c[0]=-1;
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[l]==c[k]) for(int i=1;i<s-m[l];i++) upd(fl[l][r][i+m[l]],f[l+1][k-1]+fl[k][r][i]);
upd(fr[l][r][m[r]],f[l][r-1]);
for(int k=l;k<r;k++) if(c[r]==c[k]) for(int i=1;i<s-m[r];i++) upd(fr[l][r][i+m[r]],f[k+1][r-1]+fr[l][k][i]);
if(c[l-1]==c[r+1]) continue;
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;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11548kb
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: 11484kb
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: 8ms
memory: 11560kb
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: 0
Accepted
time: 5ms
memory: 11548kb
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:
9262990
result:
ok single line: '9262990'
Test #5:
score: -100
Wrong Answer
time: 8ms
memory: 11552kb
input:
150 10 491282 5 7 1 4 5 3 5 3 5 6 7 3 6 3 4 5 4 2 3 7 3 4 7 2 3 7 5 4 6 1 7 5 2 6 4 1 6 2 5 4 1 3 6 7 5 6 2 1 3 2 1 7 1 2 6 1 2 6 4 3 7 6 5 3 5 4 1 2 7 1 5 6 2 6 5 1 3 5 6 3 4 5 1 3 7 4 6 4 2 6 3 7 5 7 1 2 7 4 3 2 1 4 2 7 4 6 2 3 6 4 7 1 5 3 2 1 3 4 3 6 7 3 7 5 6 2 4 2 1 3 2 3 7 5 3 5 6 4 6 1 2 6 7 ...
output:
298434718
result:
wrong answer 1st lines differ - expected: '300542698', found: '298434718'