fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. //#pragma GCC optimize ("O3")
  5. //#pragma GCC target ("sse4")
  6.  
  7. using namespace std;
  8. template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
  9. template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
  10. const int MAXN = 32;
  11. const int MAXK = 5032;
  12. const int64_t inf = (int64_t)1e18;
  13.  
  14. int n, k;
  15. pair<int64_t, int> a[MAXN];
  16.  
  17. void read()
  18. {
  19. 	cin >> n >> k;
  20. 	k -= n;
  21.  
  22. 	for(int i = 0; i < n; i++)
  23. 	{
  24. 		cin >> a[i].first;
  25. 		a[i].second = i;
  26. 	}
  27. }
  28.  
  29. int64_t dp[MAXN][MAXN][MAXK];
  30. int answer[MAXN];
  31.  
  32. int64_t rec(int i, int add, int lft, int S = 0)
  33. {
  34. 	if(i == n)
  35. 		return lft == 0 ? 0 : inf; 
  36.  
  37. 	int64_t &memo = dp[i][add][lft];
  38. 	if(memo != -1)
  39. 		return memo;
  40.  
  41. 	memo = inf;
  42. 	chkmin(memo, rec(i + 1, add + 1, lft, S + a[i].first));
  43. 	for(int v = 1; v * (n - i) <= lft; v++)
  44. 		chkmin(memo, S * (n - i) + rec(i + 1, 1, lft - v * (n - i), a[i].first));
  45.  
  46. 	return memo;
  47. }
  48.  
  49. void solve()
  50. {
  51. 	sort(a, a + n);
  52. 	memset(dp, -1, sizeof(dp));
  53.  
  54. 	while(k > 1200)
  55. 	{
  56. 		k -= n;
  57. 		for(int i = 0; i < n; i++)
  58. 			answer[i]++;
  59. 	}
  60.  
  61. 	for(int i = 0; i < n; i++)
  62. 		answer[i]++;
  63.  
  64. 	cout << rec(0, 0, k) << endl;
  65.  
  66. 	int add = 0, lft = k, S = 0;
  67. 	for(int i = 0; i < n; i++)
  68. 	{
  69. 		if(rec(i, add, lft, S) == rec(i + 1, add + 1, lft, S + a[i].first))
  70. 		{
  71. 			S += a[i].first;
  72. 			add++;
  73. 		}
  74. 		else for(int v = 1; v * (n - i) <= lft; v++)
  75. 			if(rec(i, add, lft, S) == S * (n - i) + rec(i + 1, 1, lft - v * (n - i), a[i].first))
  76. 			{
  77. 				S = a[i].first;
  78. 				lft -= v * (n - i);
  79. 				add = 1;
  80.  
  81. 				for(int p = i; p < n; p++)
  82. 					answer[a[p].second] += v;
  83. 				break;
  84. 			}
  85.  
  86. 	}
  87.  
  88. 	for(int i = 0; i < n; i++)
  89. 		cout << answer[i] << " ";
  90. 	cout << endl;
  91.  
  92. }
  93.  
  94. int main()
  95. {
  96. 	ios_base::sync_with_stdio(false);
  97. 	cin.tie(NULL);
  98.  
  99. 	read();
  100. 	solve();
  101. 	return 0;
  102. }
  103.  
  104.  
Success #stdin #stdout 0s 55496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/gEbP46
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!