fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define fir first
  3. #define sec second
  4.  
  5. using namespace std;
  6.  
  7. using ll = long long;
  8.  
  9. const int maxn = 2e3 + 5;
  10. const int maxm = 3e5 + 5;
  11. const ll oo = 1e18 + 1;
  12.  
  13. ll e[maxn], s[maxm], Ps1[maxn], Len[maxn];
  14. int n, m;
  15. bool ISub1 = true, DSub1 = true;
  16.  
  17. int BSI1(ll x, int limit) {
  18. 	int l = 1, r = limit;
  19.  
  20. 	while (l <= r) {
  21. 		int mid = (l + r) / 2;
  22.  
  23. 		if (Ps1[limit] - Ps1[mid - 1] + x < 0)
  24. 			l = mid + 1;
  25. 		else r = mid - 1;
  26. 	}
  27.  
  28. 	return (l);
  29. }
  30.  
  31. int BSD1(ll x, int limit) {
  32. 	int l = limit, r = n;
  33.  
  34. 	while (l <= r) {
  35. 		int mid = (l + r) / 2;
  36.  
  37. 		if (Ps1[limit] - Ps1[mid + 1] + x < 0)
  38. 			r = mid - 1;
  39. 		else l = mid + 1;
  40. 	}
  41.  
  42. 	return (l - 1);
  43. }
  44.  
  45. void Sub1() {
  46. 	if (ISub1) {
  47. 		int limit = n;
  48. 		Ps1[0] = 0;
  49.  
  50. 		for (int i = 1; i <= n; i++)
  51. 			if (e[i] < 0) {
  52. 				Ps1[i] = Ps1[i - 1] + e[i];
  53. 			}
  54. 			else {
  55. 				limit = i - 1;
  56. 				break;
  57. 			}
  58.  
  59. 		for (int i = 1; i <= m; i++) {
  60. 			int id = BSI1(s[i], limit);
  61.  
  62. 			cout << n - id + 1 << ' ';
  63. 		}
  64.  
  65. 		return;
  66. 	}
  67. 	else {
  68. 		int limit = 1;
  69. 		ll add = 0;
  70. 		Ps1[n + 1] = 0;
  71.  
  72. 		for (int i = 1; i <= n; i++)
  73. 			if (e[i] > 0) add += e[i];
  74. 			else break;
  75.  
  76. 		for (int i = n; i; i--)
  77. 			if (e[i] < 0) {
  78. 				Ps1[i] = Ps1[i + 1] + e[i];
  79. 			}
  80. 			else {
  81. 				limit = i + 1;
  82. 				break;
  83. 			}
  84.  
  85. 		for (int i = 1; i <= m; i++) {
  86. 			int id = BSD1(s[i] + add, limit);
  87.  
  88. 			cout << id << ' ';
  89. 		}
  90.  
  91. 		return;
  92. 	}
  93. }
  94.  
  95. void Sub3() {
  96. 	int curmask = (1 << n);
  97.  
  98. 	for (int i = 0; i <= n; i++) Len[i] = -oo;
  99.  
  100. 	for (int mask = 0; mask < curmask; mask++) {
  101. 		int len = __builtin_popcount(mask);
  102.  
  103. 		ll sum = 0, ans = oo;
  104.  
  105. 		for (int id = 0; id < n; id++)
  106. 			if ((mask >> id) & 1) {
  107. 				sum += e[id + 1];
  108. 				ans = min(ans, sum);
  109. 			}
  110.  
  111. 		Len[len] = max(Len[len], ans);
  112. 	}
  113.  
  114. 	for (int i = 1; i <= m; i++)
  115. 		for (int len = n; len >= 0; len--)
  116. 			if (s[i] + Len[len] >= 0) {
  117. 				cout << len << ' ';
  118. 				break;
  119. 			}
  120. }
  121.  
  122. void Sub4() {
  123. 	for (int i = 1; i <= m; i++) {
  124. 		ll sum = s[i];
  125.  
  126. 		priority_queue<ll, vector<ll>, greater<ll>> inQue;
  127.  
  128. 		for (int j = 1; j <= n; j++)
  129. 			if (sum + e[j] >= 0) {
  130. 				inQue.push(e[j]);
  131. 				sum += e[j];
  132. 			}
  133. 			else if (!inQue.empty() && inQue.top() < e[j]) {
  134. 				ll x = inQue.top();
  135. 				inQue.pop();
  136. 				sum -= x;
  137. 				sum += e[j];
  138.  
  139. 				inQue.push(e[j]);
  140. 			}
  141.  
  142. 		cout << inQue.size() << ' ';
  143. 	}
  144. }
  145.  
  146. int main() {
  147. 	ios_base::sync_with_stdio(false);
  148. 	cin.tie(0); cout.tie(0);
  149. 	cin >> n >> m;
  150.  
  151. 	for (int i = 1; i <= n; i++) {
  152. 		cin >> e[i];
  153.  
  154. 		if (i >= 2)
  155. 			if (e[i] < e[i - 1])
  156. 				ISub1 = false;
  157. 			else if (e[i] > e[i - 1])
  158. 				DSub1 = false;
  159. 	}
  160.  
  161. 	for (int i = 1; i <= m; i++) cin >> s[i];
  162.  
  163. 	if (ISub1 || DSub1) {
  164. 		Sub1();
  165. 		return 0;
  166. 	}
  167.  
  168. 	if (n <= 21) {
  169. 		Sub3();
  170. 		return 0;
  171. 	}
  172.  
  173. 	if (m <= 5005) {
  174. 		Sub4();
  175. 		return 0;
  176. 	}
  177. 	return 0;
  178. }
Success #stdin #stdout 0.01s 5384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kjxFFk
language:
C++ (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!