fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define C make_pair
  3. #define ll long long
  4. #define all(a) a.begin(),a.end()
  5. #define name "task"
  6. #define ln "\n"
  7. using namespace std;
  8.  
  9. ll n,k;
  10. const int maxN=200+9;
  11. ll a[maxN];
  12. vector<ll> two(maxN,0);
  13. vector<ll> five(maxN,0);
  14. void solve() {
  15. 	cin>>n>>k;
  16. 	for(int i=1;i<=n;++i){
  17. 		cin>>a[i];
  18. 		while(a[i]%2==0){
  19. 			a[i]/=2;
  20. 			++two[i];
  21. 		}
  22. 		while(a[i]%5==0){
  23. 			a[i]/=5;
  24. 			++five[i];
  25. 		}
  26. 		//cout<<two[i]<<" "<<five[i]<<ln;
  27. 	}
  28. 	ll dp[2][209][210*25];
  29. 	memset(dp,-0x3f,sizeof(dp)); dp[0][0][0]=0;
  30. 	for(int i=0;i<n;++i){
  31. 		for(int j=0;j<=k;++j){
  32. 			for(int x=0;x<=25*209;++x){
  33. 				if(dp[i%2][j][x]>=0){
  34. 					dp[(i+1)%2][j][x]=max(dp[(i+1)%2][j][x],dp[i%2][j][x]);
  35. 					if(x+five[i+1]<=25*209 && j+1<=k)
  36. 						dp[(i+1)%2][j+1][x+five[i+1]]=max(dp[(i+1)%2][j+1][x+five[i+1]],dp[i%2][j][x]+two[i+1]);
  37. 				}
  38. 			}
  39. 		}
  40. 	}
  41. 	ll res=0;
  42. 	for(int i=1;i<=25*209;++i){
  43. 		res=max(res,min(dp[n%2][k][i],i*1LL));
  44. 		//cout<<dp[n%2][k][i]<<" "<<i<<ln;
  45. 	}
  46. 	cout<<res;
  47. }
  48. int main(){
  49.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  50.     if(fopen(name".inp","r")){
  51.         freopen(name".inp","r",stdin);
  52.         freopen(name".out","w",stdout);
  53.     }
  54.     solve();
  55. }
  56.  
Success #stdin #stdout 0.01s 20700KB
comments (?)
stdin
copy 
10 10
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000
stdout
copy 
180
https://ideone.com/R2nX9B
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!