Advertisement
Josif_tepe

Untitled

Nov 3rd, 2023
622
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <fstream>
  5. #include <cstring>
  6. using namespace std;
  7. typedef long long ll;
  8. const int maxn = 202;
  9. const int INF = 1e9;
  10. int n, k;
  11. int arr[maxn];
  12. int power_of_two[maxn], power_of_five[maxn];
  13. void factor(int at, ll x) {
  14.     power_of_two[at] = 0;
  15.     power_of_five[at] = 0;
  16.     while(x % 2 == 0) {
  17.         power_of_two[at]++;
  18.         x /= 2;
  19.     }
  20.     while(x % 5 == 0) {
  21.         power_of_five[at]++;
  22.         x /= 5;
  23.     }
  24. }
  25. int dp[2][maxn][5206];
  26. int main() {
  27.     ios_base::sync_with_stdio(false);
  28.     cin >> n >> k;
  29.    
  30.     for(int i = 0; i < n; i++) {
  31.         cin >> arr[i];
  32.         factor(i, arr[i]);
  33.     }
  34.     for(int at = n; at >= 0; at--) {
  35.         int current_at = at % 2;
  36.         int prev_at = 1 - (at % 2);
  37.         for(int taken = 0; taken <= k; taken++) {
  38.             for(int five = 0; five <= 5200; five++) {
  39.                 if(at == n or taken == 0) {
  40.                     if(taken > 0 or five > 0) {
  41.                         dp[current_at][taken][five] = -INF;
  42.                     }
  43.                     else {
  44.                         dp[current_at][taken][five] = 0;
  45.                     }
  46.                 }
  47.                 else {
  48.                     dp[current_at][taken][five] = dp[prev_at][taken][five];
  49.                     if(taken > 0) {
  50.                         dp[current_at][taken][five] = max(dp[current_at][taken][five], dp[prev_at][taken - 1][five - power_of_five[at]] + power_of_two[at]);
  51.                     }
  52.                 }
  53.             }
  54.         }
  55.     }
  56.     int res = 0;
  57.     for(int i = 0; i <= 5200; i++) {
  58.         if(dp[0][k][i] >= i) {
  59.             res = i;
  60.         }
  61.     }
  62.     cout << res << endl;
  63.     return 0;
  64. }
  65.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement