QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#536477 | #7988. 史莱姆工厂 | tarjen | WA | 9ms | 3792kb | C++20 | 1.1kb | 2024-08-29 13:34:10 | 2024-08-29 13:34:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=151;
int dp[maxn][maxn],vis[maxn][maxn];
void gmax(int &x,int y){
if(y>x)x=y;
}
int n,k,w;
int c[maxn],m[maxn],p[maxn];
vector<int> ve[maxn];
int dfs(int l,int r){
if(l>r)return 0;
if(vis[l][r])return dp[l][r];
int res=-2e9;
if(l==r)res=p[k]-(k-m[l])*w;
else{
for(int i=l;i<=r;i++){
auto it=lower_bound(ve[c[i]].begin(),ve[c[i]].end(),i);
for(int now=0,pr=l,nowans=0;it!=ve[c[i]].end()&&*it<=r;it++){
now+=m[*it];
nowans+=dfs(pr,*it-1);
gmax(res,nowans+dfs((*it)+1,r)+(now>=k?p[now]:p[k]-(k-now)*w));
pr=(*it)+1;
if(now>=k)break;
}
}
}
vis[l][r]=1;
// cout<<"l="<<l<<" r="<<r<<" dp="<<res<<endl;
return dp[l][r]=res;
}
int main()
{
cin>>n>>k>>w;
for(int i=1;i<=n;i++)cin>>c[i],ve[c[i]].push_back(i);
for(int i=1;i<=n;i++)cin>>m[i];
for(int i=k;i<=k*2-2;i++)cin>>p[i];
cout<<dfs(1,n);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3700kb
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: 3616kb
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: 9ms
memory: 3748kb
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: 8ms
memory: 3792kb
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'