QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#536477#7988. 史莱姆工厂tarjenWA 9ms3792kbC++201.1kb2024-08-29 13:34:102024-08-29 13:34:10

Judging History

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

  • [2024-08-29 13:34:10]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:3792kb
  • [2024-08-29 13:34:10]
  • 提交

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);
}

詳細信息

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'