Submission #669738

#	Time	Username	Problem	Language	Result	Execution time	Memory
669738		omkarbajaj073	Visiting Singapore (NOI20_visitingsingapore)	C++17	29 / 100	245 ms	196252 KiB

VisitingSingapore

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5005, MAX_K = 1005;
const int inf = 1e9;

int K, N, M, V[MAX_K], S[MAX_N], T[MAX_N], a, b, dp[MAX_N][MAX_N][2];

int main() {
  
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> K >> N >> M >> a >> b;
  for (int i = 0; i < K; i++) cin >> V[i];
  for (int i = 1; i <= N; i++) {
    cin >> S[i]; S[i]--;
  }
  for (int i = 1; i <= M; i++) {
    cin >> T[i]; T[i]--;
  }

  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= M; j++) {
      dp[i][j][0] = dp[i][j][1] = -inf;
    }
  }

  for (int j = 0; j <= M; j++) 
    dp[0][j][0] = a + j * b;

  for (int i = 0; i <= N; i++) 
    dp[i][0][0] = 0;
  
  

  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      // skipping a day
      if (i != 1)
        dp[i][j][0] = max(dp[i-1][j][0] + b, dp[i-1][j][1] + a + b);
      else 
        dp[i][j][0] = max(dp[i-1][j][0] + a + b, dp[i-1][j][1] + a + b);

      if (j != 1)
        dp[i][j][0] = max(dp[i][j][0], max(dp[i][j-1][1] + a + b, dp[i][j-1][0] + b));
      else 
        dp[i][j][0] = max(dp[i][j][0], max(dp[i][j-1][1] + a + b, dp[i][j-1][0] + a + b));

      if (S[i] == T[j]) {
        int tmp = (j == 1) ? 0 : ((j-1) * b + a);
        dp[i][j][1] = max(max(dp[i-1][j-1][0], dp[i-1][j-1][1]), tmp) + V[S[i]];
      }

      // cout << i << ", " << j << " dp: " << dp[i][j][0] << ", " << dp[i][j][1] << endl;
    }
  }

  int ans = a + M * b;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      if (j == M) ans = max(ans, max(dp[i][j][0], dp[i][j][1]));
      else ans = max(ans, max(dp[i][j][0] + (M-j) * b, dp[i][j][1]  + a + (M-j)*b));
    }
  }

  cout << ans << endl;

  return 0;
}

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