fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.File;
  4. import java.io.FileReader;
  5. import java.io.FileWriter;
  6. import java.io.IOException;
  7. import java.util.Arrays;
  8. import java.util.Comparator;
  9. import java.util.PriorityQueue;
  10. import java.util.Vector;
  11.  
  12. public class Main {
  13.  
  14. 	public static void main(String[] args) throws IOException {
  15. 		BufferedReader br =  new BufferedReader(new FileReader(new File("input.txt")));
  16. 		String[] nAuthority = br.readLine().split(" ");
  17. 		int n = Integer.parseInt(nAuthority[0]);
  18. 		int authority = Integer.parseInt(nAuthority[1]);
  19. 		int[] a = new int [n], b = new int [n];
  20. 		for (int i = 0; i < n; ++i) {
  21. 			String[] ab = br.readLine().split(" ");
  22. 			a[i] = Integer.parseInt(ab[0]);
  23. 			b[i] = Integer.parseInt(ab[1]);
  24. 		}
  25.  
  26. 		Friend[] convincesFriends = (new Main(authority, a, b)).convinceMaxFriends();
  27. 		BufferedWriter bw = new BufferedWriter(new FileWriter("output.txt"));
  28. 		bw.write(convincesFriends.length+"\n");
  29. 		for (Friend friend : convincesFriends) {
  30. 			bw.write(friend.index+" ");
  31. 		}
  32. 		bw.flush();
  33. 	}
  34.  
  35. 	private Friend[] friends;
  36. 	private int authority;
  37. 	private Main(int authority, int a[], int b[]) {
  38. 		this.authority = authority;
  39. 		friends = new Friend[a.length];
  40. 		for (int i = 0; i < friends.length; ++i) {
  41. 			friends[i] = new Friend(a[i], b[i], i+1);
  42. 		}
  43. 	}
  44.  
  45. 	Comparator < Friend > sortCompare = new Comparator<Friend>() {
  46. 		@Override
  47. 		public int compare(Friend o1, Friend o2) {
  48. 			return o2.a+o2.b-o1.a-o1.b;
  49. 		}
  50. 	};
  51.  
  52. 	private Friend[] solveNegativeDp(Friend[] negative) {
  53. 		Arrays.sort(negative, sortCompare);
  54.  
  55. 		Integer[][] maxBSum = new Integer[negative.length+1][negative.length+1];
  56. 		maxBSum[0][0] = 0;
  57. 		for (int i = 1; i <= negative.length; ++i) {
  58. 			maxBSum[i][0] = 0;
  59. 			for (int j = 1; j <= negative.length; ++j) {
  60. 				if (maxBSum[i-1][j-1] != null && authority + maxBSum[i-1][j-1] >= negative[i-1].a) {
  61. 					maxBSum[i][j] = maxBSum[i-1][j-1] + negative[i-1].b;
  62. 				}
  63. 				if (maxBSum[i][j] == null || maxBSum[i-1][j] != null && maxBSum[i-1][j] >= maxBSum[i][j]) {
  64. 					maxBSum[i][j] = maxBSum[i-1][j];
  65. 				}
  66. 			}
  67. 		}
  68.  
  69. 		int j, i = negative.length;
  70. 		for (j = negative.length; maxBSum[i][j] == null; --j);
  71.  
  72. 		Friend[] negativeAdded = new Friend[j];
  73. 		for (; i >= 0 && j > 0; --i) {
  74. 			if (maxBSum[i][j] != maxBSum[i-1][j]) {
  75. 				negativeAdded[--j] = negative[i-1];
  76. 			}
  77. 		}
  78.  
  79. 		return negativeAdded;
  80. 	}
  81.  
  82. 	private Friend[] solveNegativeGreedy(Friend[] negative) {
  83. 		Arrays.sort(negative, sortCompare);		
  84.  
  85. 		PriorityQueue<Friend> negativeAdded = new PriorityQueue<>(1, new Comparator<Friend>() {
  86. 			@Override
  87. 			public int compare(Friend o1, Friend o2) {
  88. 				return o1.b - o2.b;
  89. 			}
  90. 		});		
  91. 		for (Friend friend : negative) {
  92. 			if (authority >= friend.a) {
  93. 				authority += friend.b;
  94. 				negativeAdded.add(friend);
  95. 			} else if (!negativeAdded.isEmpty() && authority - negativeAdded.peek().b >= friend.a && negativeAdded.peek().b < friend.b) {
  96. 				authority = authority - negativeAdded.poll().b + friend.b;
  97. 				negativeAdded.add(friend);
  98. 			}
  99. 		}
  100.  
  101. 		Friend[] answer = negativeAdded.toArray(new Friend[negativeAdded.size()]);
  102. 		Arrays.sort(answer, sortCompare);
  103. 		return answer;
  104. 	}
  105.  
  106. 	private Friend[] convinceMaxFriends(){
  107. 		Vector < Friend > convinced = new Vector<>();
  108. 		Vector < Friend > positive = new Vector<>();
  109. 		for (int i = 0; i < friends.length; ++i) {
  110. 			if (friends[i].b >= 0) {
  111. 				positive.add(friends[i]);
  112. 			}
  113. 		}
  114.  
  115. 		positive.sort(new Comparator<Friend>() {
  116. 			@Override
  117. 			public int compare(Friend o1, Friend o2) {
  118. 				return o1.a - o2.a;
  119. 			}
  120. 		});
  121.  
  122. 		for (Friend friend : positive) {
  123. 			if (authority >= friend.a) {
  124. 				authority += friend.b;
  125. 				convinced.add(friend);
  126. 			}
  127. 		}
  128.  
  129. 		Friend[] negative = new Friend[friends.length - positive.size()];
  130. 		for (int i = 0, j = 0; i < friends.length; ++i) {
  131. 			if (friends[i].b < 0) {
  132. 				negative[j++] = friends[i];
  133. 			}
  134. 		}
  135.  
  136.  
  137. 		convinced.addAll(Arrays.asList(solveNegativeGreedy(negative)));
  138.  
  139. 		return convinced.toArray(new Friend[convinced.size()]);
  140. 	}
  141.  
  142. 	private class Friend {
  143. 		private int a, b, index;
  144. 		private Friend(int a, int b, int index) {
  145. 			this.a = a;
  146. 			this.b = b;
  147. 			this.index = index;
  148. 		}
  149. 	}
  150.  
  151. }
  152.  
Runtime error #stdin #stdout #stderr 0.1s 320576KB
comments (?)
stdin
copy 
5 1
1 3
6 -5
6 -4
2 2
2 -1
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.io.FileNotFoundException: input.txt (No such file or directory)
	at java.io.FileInputStream.open0(Native Method)
	at java.io.FileInputStream.open(FileInputStream.java:195)
	at java.io.FileInputStream.<init>(FileInputStream.java:138)
	at java.io.FileReader.<init>(FileReader.java:72)
	at Main.main(Main.java:15)
https://ideone.com/kpAqgc
language:
Java (HotSpot 12)
created:
8 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!