Submission #680199

#	Time	Username	Problem	Language	Result	Execution time	Memory
680199		abcvuitunggio	Visiting Singapore (NOI20_visitingsingapore)	C++17	100 / 100	504 ms	848 KiB

VisitingSingapore

#include <iostream>
#define int long long
using namespace std;
const int INF=1e18;
int dp[2][5001][2][2],k,n,m,a,b,v[1001],s[5001],t[5001],res=-INF;
int32_t main(){
    ios_base::sync_with_stdio(NULL);
    cin >> k >> n >> m >> a >> b;
    for (int i=1;i<=k;i++)
        cin >> v[i];
    for (int i=1;i<=n;i++)
        cin >> s[i];
    for (int i=0;i<m;i++)
        cin >> t[i];
    for (int i=0;i<=m;i++){
        for (int j=0;j<2;j++)
            for (int k=0;k<2;k++){
                dp[0][i][j][k]=(i==m?0:a*k+b*(m-i));
                dp[1][i][j][k]=-INF;
            }
    }
    for (int i=n;i>=1;i--){
        for (int j=m;j>=0;j--){
            for (int k=0;k<2;k++)
                for (int l=0;l<2;l++){
                    dp[1][j][k][l]=max((j==m?0:a*k+b*(m-j)),dp[0][j][0][l]+a*k+b);
                    if (j==m)
                        continue;
                    dp[1][j][k][l]=max(dp[1][j][k][l],max((s[i]==t[j]?dp[0][j+1][1][1]+v[t[j]]:-INF),dp[1][j+1][k][0]+b+a*l));
                }
        }
        res=max(res,dp[1][0][1][1]);
        for (int j=m;j>=0;j--){
            for (int k=0;k<2;k++)
                for (int l=0;l<2;l++){
                    swap(dp[0][j][k][l],dp[1][j][k][l]);
                    dp[1][j][k][l]=-INF;
                }
        }
    }
    cout << res;
}

• 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