fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5. const int MAXN = (int)1e5 + 42;
  6. const int MAXM = (int)10;
  7.  
  8. int n, k;
  9. int m[MAXN];
  10. int64_t a[MAXN][MAXM];
  11.  
  12. void read()
  13. {
  14. 	cin >> n >> k;
  15. 	for(int i = 0; i < n; i++)
  16. 	{
  17. 		cin >> m[i];
  18. 		for(int j = 0; j < m[i]; j++)
  19. 			cin >> a[i][j];
  20. 	}
  21. }
  22.  
  23. int64_t sum;
  24.  
  25. bool check(int64_t val)
  26. {
  27. 	if(val < sum) return false;
  28. 	val -= sum;
  29.  
  30. 	int64_t ret = 1;
  31. 	if(ret == k) return true;
  32.  
  33. 	map<int64_t, int64_t> cnt;
  34. 	cnt[val] = 1;
  35.  
  36. 	for(int i = 0; i < n; i++)
  37. 	{
  38. 		vector<pair<int64_t, int64_t>> to_add;
  39.  
  40. 		for(int j = 1; j < m[i]; j++)
  41. 		{
  42. 			for(auto iter = prev(cnt.end()); ; --iter)
  43. 			{
  44. 				auto it = *iter;
  45.  
  46. 				if(it.first >= a[i][j])
  47. 				{
  48. 					ret += it.second;
  49. 					if(ret >= k) return true;
  50. 					to_add.push_back({it.first - a[i][j], it.second});
  51. 				}
  52. 				else break;
  53.  
  54. 				if(iter == cnt.begin()) break;
  55. 			}
  56. 		}
  57.  
  58. 		for(auto it: to_add)
  59. 			cnt[it.first] += it.second;
  60. 	}
  61.  
  62. 	return (ret >= k);
  63. }
  64.  
  65. void solve()
  66. {
  67. 	sum = 0;
  68. 	for(int i = n - 1; i >= 0; i--)
  69. 		sort(a[i], a[i] + m[i]), sum += a[i][0];
  70.  
  71.     for(int i = 0; i < n; i++)
  72.     	for(int j = 1; j < m[i]; j++)
  73. 			a[i][j] -= a[i][0];
  74.  
  75.     int64_t low = 0, high = (int64_t)1e17 + 42, mid, ret;
  76.  
  77.     while(low <= high)
  78. 	{
  79. 		mid = (low + high) >> 1ll;
  80. 		if(check(mid)) high = mid - 1, ret = mid;
  81. 		else low = mid + 1;
  82. 	}
  83.  
  84.     int64_t cnt = 1, ans = sum;
  85.     ret--;
  86. 	ret -= sum;
  87.  
  88.     map<int64_t, pair<int64_t, int64_t> > st;
  89.     st[ret] = {1, sum};
  90.  
  91.     if(k == cnt)
  92. 	{
  93. 		cout << ans << endl;
  94. 		return;
  95. 	}
  96.  
  97. 	for(int i = 0; i < n; i++)
  98. 	{
  99. 		vector<pair<int64_t, pair<int64_t, int64_t>>> to_add;
  100. 		for(int j = 1; j < m[i]; j++)
  101. 		{
  102. 			for(auto iter = prev(st.end()); ; --iter)
  103. 			{
  104. 				auto it = *iter;
  105. 				if(it.first >= a[i][j])
  106. 				{
  107. 					int64_t delta = it.second.first;
  108.  
  109.                     cnt += delta;
  110.                     ans += (it.second.second + a[i][j]) * delta;
  111.  
  112. 					to_add.push_back({it.first - a[i][j], {delta, delta * (it.second.second + a[i][j])}});
  113. 				}
  114. 				else break;
  115.  
  116. 				if(iter == st.begin()) break;
  117. 			}
  118. 		}
  119.  
  120. 		for(auto it: to_add)
  121. 		{
  122. 			st[it.first].first += it.second.first;
  123. 			st[it.first].second += it.second.second;
  124. 		}
  125. 	}
  126.  
  127. 	while(cnt < k) cnt++, ans += ret + 1 + sum;
  128. 	cout << ans << endl;
  129. }
  130.  
  131. int main()
  132. {
  133. 	freopen("roboherd.in", "r", stdin);
  134. 	freopen("roboherd.out", "w", stdout);
  135.  
  136. 	ios_base::sync_with_stdio(false);
  137. 	cin.tie(NULL);
  138.  
  139. 	read();
  140. 	solve();
  141. 	return 0;
  142. }
  143.  
Runtime error #stdin #stdout #stderr 0s 11680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure'
  what():  basic_filebuf::underflow error reading the file
https://ideone.com/Zupv7Z
language:
C++14 (gcc 8.3)
created:
8 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!