Submission #1023262

#TimeUsernameProblemLanguageResultExecution timeMemory
1023262avighnaVisiting Singapore (NOI20_visitingsingapore)C++17
4 / 100
27 ms504 KiB
#include <bits/stdc++.h>

const int N = 5001;

int dp[N][2][2][2];

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

  int k, n, m, a, b;
  std::cin >> k >> n >> m >> a >> b;
  std::vector<int> v(k), s(n), t(m);
  for (auto &i : v) {
    std::cin >> i;
  }
  for (auto &i : s) {
    std::cin >> i;
  }
  for (auto &i : t) {
    std::cin >> i;
  }

  // dp[i][j][b1][b2] = the maximum happiness when we start from index i in t
  // and j in s. b1 is 1 if we picked the last element in t, else 0. same for
  // b2.

  int ans = a + m * b;
  for (int i = m; i >= 0; --i) {
    for (int j = n; j >= 0; --j) {
      for (int b1 = 0; b1 <= 1; ++b1) {
        for (int b2 = 0; b2 <= 1; ++b2) {
          if (i == m and j == n) {
            continue;
          }
          if (i == m) {
            continue;
          }
          if (j == n) {
            dp[i][j][b1][b2] = b1 * a + (m - i) * b;
            continue;
          }

          dp[i][j % 2][b1][b2] =
              std::max(dp[i + 1][j % 2][0][b2] + b1 * a + b,
                       dp[i][(j + 1) % 2][b1][0] + b2 * a + b);
          if (t[i] == s[j]) {
            dp[i][j % 2][b1][b2] =
                std::max(dp[i][j % 2][b1][b2],
                         v[t[i] - 1] + dp[i + 1][(j + 1) % 2][1][1]);
          }
        }
      }
      if (i == 0 and j != n) {
        ans = std::max(ans, dp[0][j % 2][1][1]);
      }
    }
  }
  std::cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...