oj.uz

Submission #1023267

# Submission time Handle Problem Language Result Execution time Memory
1023267 2024-07-14T14:26:36 Z avighna Visiting Singapore (NOI20_visitingsingapore) C++17
4 / 100
 44 ms 500 KB 
#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 b1 = 0; b1 <= 1; ++b1) {
      for (int b2 = 0; b2 <= 1; ++b2) {
        for (int j = n; j >= 0; --j) {
          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) {
            ans = std::max(ans, dp[0][j % 2][1][1]);
          }
        }
      }
    }
  }
  std::cout << ans << "\n";
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 13 ms 492 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 8 ms 472 KB Output is correct
10 Correct 15 ms 348 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 13 ms 492 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 8 ms 472 KB Output is correct
10 Correct 15 ms 348 KB Output is correct
11 Incorrect 1 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -