fork(1) download
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <climits>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <deque>
  8. #include <functional>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <list>
  12. #include <map>
  13. #include <queue>
  14. #include <set>
  15. #include <sstream>
  16. #include <stack>
  17. #include <string>
  18. #include <vector>
  19.  
  20. using namespace std;
  21.  
  22. #define FOR(i, N) for(int i = 0; i < N; i++)
  23. #define FOR1e(i, N) for(int i = 1; i <= N; i++)
  24. #define REP(i, M, N) for(int i = M; i < N; i++)
  25. #define REPe(i, M, N) for(int i = M; i <= N; i++)
  26. #define sc(N) scanf("%d", &N)
  27. #define scsc(M, N) scanf("%d %d", &M, &N)
  28. #define gt(s) getline(cin, s)
  29. #define all(s) s.begin(), s.end()
  30. #define ll long long
  31. #define vi vector <int>
  32. #define pii pair <int, int>
  33. #define ss stringstream
  34. #define pq priority_queue
  35. #define mp make_pair
  36. #define pb push_back
  37. #define ms(a, v) memset(a, v, sizeof a)
  38.  
  39. const int MAX = 1e5 + 1;
  40. const int MOD = 1000000007;
  41.  
  42. int dr[] = {0, -1, 0, 1};
  43. int dc[] = {1, 0, -1, 0};
  44.  
  45. inline int Pow(int b, int p) {if(!p) return 1; int sq = Pow(b, p >> 1); sq *= sq; if(p&1) sq *= b; return sq;}
  46. inline int gcd(int a, int b) {if(!a) return b; return gcd(b % a, a);}
  47.  
  48. int t, n, k, arr[105];
  49. ll dp[105][105];
  50.  
  51. ll solve(int i, int curK, ll val){
  52. if(curK == k){
  53. if(val % 9 == 0)
  54. return val;
  55. return -(1 << 62);
  56. }
  57. if(i == n) //we reached the end before concatinating K numbers.
  58. return -(1 << 62);
  59. ll &ret = dp[i][curK];
  60. if(ret != -1)
  61. return ret;
  62. ret = -(1 << 62);
  63. //(0 / 1): take it or leave it
  64. return ret = max(ret, max(solve(i + 1, curK + 1, val * 10 + arr[i]), solve(i + 1, curK, val)));
  65. }
  66.  
  67. int main(){
  68. #ifndef ONLINE_JUDGE
  69. freopen("in.txt", "r", stdin);
  70. #endif
  71. sc(t);
  72. while(t--){
  73. scsc(n, k);
  74. FOR(i, n)
  75. sc(arr[i]);
  76. sort(arr, arr + n, greater <int>());
  77. ms(dp, -1);
  78. ll ans = solve(0, 0, 0);
  79. if(ans == -(1 << 62))
  80. puts("-1");
  81. else
  82. printf("%lld\n", ans);
  83. }
  84. return 0;
  85. }
  86.  
Success #stdin #stdout 0s 3380KB
stdin
Standard input is empty
stdout
Standard output is empty