Submission #1023251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023251		avighna	Visiting Singapore (NOI20_visitingsingapore)	C++17	23 / 100	258 ms	262144 KiB

VisitingSingapore

#include <bits/stdc++.h>

const int N = 5001, M = 5001;

int dp[N][M][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][b1][b2] = std::max(dp[i + 1][j][0][b2] + b1 * a + b,
                                      dp[i][j + 1][b1][0] + b2 * a + b);
          if (t[i] == s[j]) {
            dp[i][j][b1][b2] = std::max(dp[i][j][b1][b2],
                                        v[t[i] - 1] + dp[i + 1][j + 1][1][1]);
          }
        }
      }
      if (i == 0 and j != n) {
        ans = std::max(ans, dp[0][j][1][1]);
      }
    }
  }
  std::cout << ans << "\n";
}

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