Submission #298255

#	Time	Username	Problem	Language	Result	Execution time	Memory
298255		beso123	Visiting Singapore (NOI20_visitingsingapore)	C++14	23 / 100	171 ms	262148 KiB

VisitingSingapore

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define inf -1e9
using namespace std;
const int N=5003;
int n,m,q,a,b;
int dp[N][N][4],h[N],s[N],t[N];
main(){
cin>>q>>n>>m>>a>>b;
for(int k=1;k<=q;k++)
    cin>>h[k];
for(int k=1;k<=n;k++)
    cin>>s[k];
for(int k=1;k<=m;k++)
    cin>>t[k];
    int ans=a+b*m;
for(int k=0;k<=n;k++){
    dp[k][0][0]=inf;
     dp[k][0][1]=inf;
      dp[k][0][2]=inf;
       dp[k][0][3]=inf;
}
for(int i=0;i<=m;i++){
    dp[0][i][0]=inf;
     dp[0][i][1]=inf;
      dp[0][i][2]=inf;
       dp[0][i][3]=inf;
}
for(int k=1;k<=n;k++){
    for(int i=1;i<=m;i++){
        dp[k][i][0]=max(dp[k][i-1][0],dp[k-1][i][0])+b;
        dp[k][i][1]=dp[k-1][i][1]+b;
        dp[k][i][2]=dp[k][i-1][2]+b;
        if(s[k]==t[i]){
        dp[k][i][3]=h[t[i]];
        if(i!=1)
            dp[k][i][3]+=a+(i-1)*b;
        dp[k][i][3]=max(dp[k][i][3],
                        max(dp[k-1][i-1][0]+(2*a)+h[t[i]],
                            max(dp[k-1][i-1][1]+a+h[t[i]],
                                max(dp[k-1][i-1][2]+a+h[t[i]],dp[k-1][i-1][3]+h[t[i]]))));
        dp[k][i][0]=max(dp[k][i][0],dp[k][i][3]);
        dp[k][i][1]=max(dp[k][i][1],dp[k][i][3]);
        dp[k][i][2]=max(dp[k][i][2],dp[k][i][3]);
        int pas=dp[k][i][3]+b*(m-i);
        if(i!=m)
            pas+=a;
        ans=max(ans,pas);
        }
        else dp[k][i][3]=inf;
    }
}
cout<<ans;
return 0;
}

Compilation message (stderr)

VisitingSingapore.cpp:11:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main(){
      |      ^

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 0 / 12
• Subtask 4: 0 / 7
• Subtask 5: 0 / 8
• Subtask 6: 13 / 13
• Subtask 7: 0 / 50