fork download
copy 
  1.  
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. int a[250000], b[250000];
  10.  
  11. int main() {
  12. 	int n;
  13. 	scanf("%d", &n);
  14. 	for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
  15. 	for (int i = 0; i < n; i ++) scanf("%d", &b[i]);
  16.  
  17. 	long long limit = 0, sum = 0;
  18. 	priority_queue< pair<int, int> > Q;
  19. 	for (int i = 0; i < n; i ++) {
  20. 		limit += a[i];
  21. 		if (sum + b[i] <= limit) {
  22. 			sum += b[i];
  23. 			Q.push(make_pair(b[i], i));
  24. 		} else if (! Q.empty() && Q.top().first > b[i]) {
  25. 			sum -= Q.top().first;
  26. 			Q.pop();
  27. 			sum += b[i];
  28. 			Q.push(make_pair(b[i], i));
  29. 		}
  30. 	}
  31.  
  32. 	vector<int> ans;
  33. 	while (! Q.empty()) {
  34. 		ans.push_back(Q.top().second);
  35. 		Q.pop();
  36. 	}
  37. 	sort(ans.begin(), ans.end());
  38. 	printf("%d\n", (int)ans.size());
  39. 	for (int i = 0; i < ans.size(); i ++)
  40. 		if (i < ans.size() - 1) printf("%d ", ans[i] + 1); else printf("%d\n", ans[i] + 1);
  41.  
  42. 	return 0;
  43. }
  44.  
Success #stdin #stdout 0.02s 4816KB
comments (?)
stdin
copy 
6
2 2 1 2 1 0
1 2 2 3 4 4
stdout
copy 
3
1 2 3
https://ideone.com/Pbh1w
language:
C++ (gcc 8.3)
created:
14 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!