Submission #680203

#	Time	Username	Problem	Language	Result	Execution time	Memory
680203		abcvuitunggio	Visiting Singapore (NOI20_visitingsingapore)	C++17	100 / 100	363 ms	844 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.tie(nullptr);
    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[n&1^1][i][j][k]=(i==m?0:a*k+b*(m-i));
                dp[n&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[i&1][j][k][l]=max((j==m?0:a*k+b*(m-j)),dp[i&1^1][j][0][l]+a*k+b);
                    if (j==m)
                        continue;
                    dp[i&1][j][k][l]=max(dp[i&1][j][k][l],max((s[i]==t[j]?dp[i&1^1][j+1][1][1]+v[t[j]]:-INF),dp[i&1][j+1][k][0]+b+a*l));
                }
        }
        res=max(res,dp[i&1][0][1][1]);
    }
    cout << res;
}

Compilation message (stderr)

VisitingSingapore.cpp: In function 'int32_t main()':
VisitingSingapore.cpp:18:21: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   18 |                 dp[n&1^1][i][j][k]=(i==m?0:a*k+b*(m-i));
      |                    ~^~
VisitingSingapore.cpp:26:67: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   26 |                     dp[i&1][j][k][l]=max((j==m?0:a*k+b*(m-j)),dp[i&1^1][j][0][l]+a*k+b);
      |                                                                  ~^~
VisitingSingapore.cpp:29:79: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   29 |                     dp[i&1][j][k][l]=max(dp[i&1][j][k][l],max((s[i]==t[j]?dp[i&1^1][j+1][1][1]+v[t[j]]:-INF),dp[i&1][j+1][k][0]+b+a*l));
      |                                                                              ~^~

• 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