lastzero.cpp

#include<iostream>
#include<cstdlib>
#include<vector>

#define long long long
#define nln '\n'

using namespace std;

pair<long, long> twofive(long n)
{
   long t = 0, f = 0;
   while (n % 2 == 0){
        ++t;
        n /= 2;
   }
   while (n % 5 == 0){
        ++f;
        n /= 5;
   }
   return {t, f};
}

int main()
{
    // Input
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    //freopen("lastzero.inp", "r", stdin);
    long n, k;
    cin >> n >> k;
    vector<long> a(n+1, 0), t(n+1, 0), f(n+1, 0);
    for (long i = 1; i <= n; ++i){
        cin >> a[i];
        pair<long, long> tem = twofive(a[i]);
        t[i] = tem.first;
        f[i] = tem.second;
    }
    // Process
    // Init dp array
    vector<vector<vector<long>>> dp(n+1);
    for (long i = 0; i <= n; ++i){
        dp[i].resize(k+1);
        for (long j = 0; j <= k; ++j)
            dp[i][j].resize(30*n+1, -30*n);
    }
    dp[0][0][0] = 0;
    for (long idx = 1; idx <= n; ++idx)
        for (long cnt = 0; cnt <= k; ++cnt)
            for (long two = 0; two <= 30*n; ++two)
                if (cnt > 0 && two >= t[idx] && dp[idx-1][cnt][two] < dp[idx-1][cnt-1][two-t[idx]]+f[idx])
                    dp[idx][cnt][two] = dp[idx-1][cnt-1][two-t[idx]]+f[idx];
                else
                    dp[idx][cnt][two] = dp[idx-1][cnt][two];
    long ans = 0;
    for (long two = 0; two <= 30*n; ++two){
        dp[n][k][two] = (dp[n][k][two] < two) ? dp[n][k][two] : two;
        ans = (ans >= dp[n][k][two]) ? ans : dp[n][k][two];
    }
    cout << ans << nln;
    return 0;
}