Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cstdint>
- int main () {
- std::int32_t Tca;
- std::cin >> Tca;
- for(std::int32_t tc = 1; tc <= Tca; tc++) {
- std::int32_t N, M;
- std::cin >> N >> M;
- std::vector<std::int32_t> T, V;
- T.reserve(N);
- V.reserve(M);
- // Reading visitors
- for(std::int32_t t = 0; t < N; t++) {
- std::int32_t t_input;
- std::cin >> t_input;
- T.push_back(t_input);
- }
- // Reading volunteers
- for(std::int32_t v = 0; v < M; v++) {
- std::int32_t v_input;
- std::cin >> v_input;
- V.push_back(v_input);
- }
- std::vector<std::vector<std::int32_t>> DP(
- N, std::vector<std::int32_t>(M, 0)
- );
- // Tourist and volunterr or just visitor
- DP.at(0).at(0) = T.at(0) < V.at(0) ? 2 : 1;
- // Volunter used for the first turist
- bool volunter_found = DP.at(0).at(0) == 2;
- // T[t] V[0]
- for(std::int32_t t = 1; t < N; t++) {
- if(!volunter_found && T.at(t) < V.at(0)) {
- DP.at(t).at(0) = DP.at(t - 1).at(0) + 2;
- volunter_found = true;
- } else {
- DP.at(t).at(0) = DP.at(t - 1).at(0) + 1;
- }
- }
- // T[0] V[v]
- volunter_found = DP.at(0).at(0) == 2;
- for(std::int32_t v = 1; v < M; v++) {
- if(!volunter_found && V.at(v) > T.at(0)) {
- DP.at(0).at(v) = DP.at(0).at(v) + 2;
- volunter_found = true;
- } else {
- DP.at(0).at(v) = DP.at(0).at(v - 1);
- }
- }
- for(std::int32_t t = 1; t < N; t++) {
- for(std::int32_t v = 1; v < M; v++) {
- if(T.at(t) < V.at(v)) {
- DP.at(t).at(v) = std::max({
- DP.at(t - 1).at(v - 1) + 2,
- DP.at(t - 1).at(v) + 1,
- DP.at(t).at(v - 1)
- });
- } else {
- DP.at(t).at(v) = std::max(
- DP.at(t - 1).at(v) + 1,
- DP.at(t).at(v - 1)
- );
- }
- }
- }
- std::cout << "Case #" << tc << ": " << DP.at(N - 1).at(M - 1) << std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement