Submission #1023268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023268		avighna	Visiting Singapore (NOI20_visitingsingapore)	C++17	100 / 100	346 ms	848 KiB

VisitingSingapore

#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 j = n; j >= 0; --j) {
    for (int i = m; i >= 0; --i) {
      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 % 2][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 and b1 == 1 and b2 == 1) {
            ans = std::max(ans, dp[0][j % 2][1][1]);
          }
        }
      }
    }
  }
  std::cout << ans << "\n";
}

• 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