Submission #298299

#	Time	Username	Problem	Language	Result	Execution time	Memory
298299		beso123	Visiting Singapore (NOI20_visitingsingapore)	C++14	100 / 100	352 ms	900 KiB

VisitingSingapore

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define inf -3e9
using namespace std;
const int N=6006;
int n,m,q,a,b;
int dp[N][4],h[N],s[N],t[N],f[N][4];
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<=m;k++){
    f[k][0]=inf;
     f[k][1]=inf;
      f[k][2]=inf;
       f[k][3]=inf;
}
dp[0][0]=inf;
dp[0][1]=inf;
dp[0][2]=inf;
dp[0][3]=inf;
for(int k=1;k<=n;k++){
    for(int i=1;i<=m;i++){
        dp[i][0]=max(dp[i-1][0],f[i][0])+b;
        dp[i][1]=f[i][1]+b;
        dp[i][2]=dp[i-1][2]+b;
        if(s[k]==t[i]){
        dp[i][3]=h[t[i]];
        if(i!=1)
            dp[i][3]+=a+(i-1)*b;
        dp[i][3]=max(dp[i][3],
                        max(f[i-1][0]+(2*a)+h[t[i]],
                            max(f[i-1][1]+a+h[t[i]],
                                max(f[i-1][2]+a+h[t[i]],f[i-1][3]+h[t[i]]))));
        dp[i][0]=max(dp[i][0],dp[i][3]);
        dp[i][1]=max(dp[i][1],dp[i][3]);
        dp[i][2]=max(dp[i][2],dp[i][3]);
        int pas=dp[i][3]+b*(m-i);
        if(i!=m)
            pas+=a;
        ans=max(ans,pas);
        }
        else dp[i][3]=inf;
    }
    for(int q=1;q<=m;q++){
            for(int i=0;i<=3;i++){
        f[q][i]=dp[q][i];
        dp[q][i]=0;
            }
    }
}
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: 12 / 12
• Subtask 4: 7 / 7
• Subtask 5: 8 / 8
• Subtask 6: 13 / 13
• Subtask 7: 50 / 50