Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- #include <fstream>
- #include <cstring>
- using namespace std;
- typedef long long ll;
- const int maxn = 202;
- const int INF = 1e9;
- int n, k;
- int arr[maxn];
- int power_of_two[maxn], power_of_five[maxn];
- void factor(int at, ll x) {
- power_of_two[at] = 0;
- power_of_five[at] = 0;
- while(x % 2 == 0) {
- power_of_two[at]++;
- x /= 2;
- }
- while(x % 5 == 0) {
- power_of_five[at]++;
- x /= 5;
- }
- }
- int dp[2][maxn][5206];
- int main() {
- ios_base::sync_with_stdio(false);
- cin >> n >> k;
- for(int i = 0; i < n; i++) {
- cin >> arr[i];
- factor(i, arr[i]);
- }
- for(int at = n; at >= 0; at--) {
- int current_at = at % 2;
- int prev_at = 1 - (at % 2);
- for(int taken = 0; taken <= k; taken++) {
- for(int five = 0; five <= 5200; five++) {
- if(at == n or taken == 0) {
- if(taken > 0 or five > 0) {
- dp[current_at][taken][five] = -INF;
- }
- else {
- dp[current_at][taken][five] = 0;
- }
- }
- else {
- dp[current_at][taken][five] = dp[prev_at][taken][five];
- if(taken > 0) {
- 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]);
- }
- }
- }
- }
- }
- int res = 0;
- for(int i = 0; i <= 5200; i++) {
- if(dp[0][k][i] >= i) {
- res = i;
- }
- }
- cout << res << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement