Advertisement
informaticage

Mostra di mojito C++11

Jun 23rd, 2023 (edited)
742
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.42 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cstdint>
  5.  
  6. int main () {
  7.     std::int32_t Tca;
  8.     std::cin >> Tca;
  9.  
  10.     for(std::int32_t tc = 1; tc <= Tca; tc++) {
  11.         std::int32_t N, M;
  12.         std::cin >> N >> M;
  13.  
  14.         std::vector<std::int32_t> T, V;
  15.         T.reserve(N);
  16.         V.reserve(M);
  17.  
  18.         // Reading visitors
  19.         for(std::int32_t t = 0; t < N; t++) {
  20.             std::int32_t t_input;
  21.             std::cin >> t_input;
  22.  
  23.             T.push_back(t_input);
  24.         }
  25.  
  26.         // Reading volunteers
  27.         for(std::int32_t v = 0; v < M; v++) {
  28.             std::int32_t v_input;
  29.             std::cin >> v_input;
  30.  
  31.             V.push_back(v_input);
  32.         }
  33.  
  34.         std::vector<std::vector<std::int32_t>> DP(
  35.             N, std::vector<std::int32_t>(M, 0)
  36.         );
  37.            
  38.         // Tourist and volunterr or just visitor
  39.         DP.at(0).at(0) = T.at(0) < V.at(0) ? 2 : 1;
  40.  
  41.         // Volunter used for the first turist
  42.         bool volunter_found = DP.at(0).at(0) == 2;
  43.         // T[t] V[0]
  44.         for(std::int32_t t = 1; t < N; t++) {
  45.             if(!volunter_found && T.at(t) < V.at(0)) {
  46.                 DP.at(t).at(0) = DP.at(t - 1).at(0) + 2;
  47.                 volunter_found = true;
  48.             } else {
  49.                 DP.at(t).at(0) = DP.at(t - 1).at(0) + 1;
  50.             }
  51.         }
  52.  
  53.         // T[0] V[v]
  54.         volunter_found = DP.at(0).at(0) == 2;
  55.         for(std::int32_t v = 1; v < M; v++) {
  56.             if(!volunter_found && V.at(v) > T.at(0)) {
  57.                 DP.at(0).at(v) = DP.at(0).at(v) + 2;
  58.                 volunter_found = true;
  59.             } else {
  60.                 DP.at(0).at(v) = DP.at(0).at(v - 1);
  61.             }
  62.         }
  63.  
  64.         for(std::int32_t t = 1; t < N; t++) {
  65.             for(std::int32_t v = 1; v < M; v++) {
  66.                 if(T.at(t) < V.at(v)) {
  67.                     DP.at(t).at(v) = std::max({
  68.                         DP.at(t - 1).at(v - 1) + 2,
  69.                         DP.at(t - 1).at(v) + 1,
  70.                         DP.at(t).at(v - 1)
  71.                     });
  72.                 } else {
  73.                     DP.at(t).at(v) = std::max(
  74.                         DP.at(t - 1).at(v) + 1,
  75.                         DP.at(t).at(v - 1)
  76.                     );
  77.                 }
  78.             }
  79.         }
  80.  
  81.         std::cout << "Case #" << tc << ": " << DP.at(N - 1).at(M - 1) << std::endl;
  82.     }
  83.    
  84.     return 0;
  85. }
  86.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement