QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#302566 | #7988. 史莱姆工厂 | PhantomThreshold | WA | 1ms | 5464kb | C++20 | 1.8kb | 2024-01-10 23:38:53 | 2024-01-10 23:38:54 |
Judging History
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]);
}
}
}
//f+g
//for(int x=1;x<K;x++) up(f[l][r][x],f[l][mid-1][x]+g[mid][r]);
//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));
}
//g+g
if( l==1||ci[l-1]!=ci[mid] )
up(g[l][r],g[l][mid-1]+fg[mid][r]);
//up(g[l][r],g[l][mid-1]+g[mid][r]);
}
//f+g
up(f[l][r][mi[l]],g[l+1][r]);
for(int k=1;k<K;k++) up(g[l][r],f[l][r][k]+pi[K]-W*(K-k));
}
}
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: 5464kb
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: -100
Wrong Answer
time: 1ms
memory: 3404kb
input:
5 7 500 2 3 2 3 2 5 6 6 6 4 1000 900 800 400 200 50
output:
2300
result:
wrong answer 1st lines differ - expected: '1400', found: '2300'