fork download 
  1. /* paiza POH! Lite
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/000512911c98eece9b0aa060fa6ce332
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. import java.io.*;
  7. import java.lang.*;
  8. import java.util.*;
  9.  
  10. class Main
  11. {
  12. 	static class Data implements Comparable<Data> {
  13. 		public int q;
  14. 		public int r;
  15. 		public double p;
  16. 		public int compareTo(Data o) {
  17. 			return (int)(o.p - this.p);
  18. 		}
  19. 	}
  20.  
  21. 	static int parseInt(String str) {
  22. 		int len = str.length();
  23. 		int n = 0;
  24. 		for (int i = 0; i < len; i++) {
  25. 			n = n * 10 + (int)(str.charAt(i) - '0');
  26. 		}
  27. 		return n;
  28. 	}
  29.  
  30. 	static Data[] data = new Data[100];
  31. 	static int all_q = 0;
  32. 	static int all_r = 0;
  33.  
  34. 	public static void main (String[] args) throws java.lang.Exception
  35. 	{
  36. 		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  37. 		int m, n, i;
  38.  
  39. 		m = parseInt(in.readLine());
  40. 		n = parseInt(in.readLine());
  41.  
  42. 		for (i = 0; i < n; i++) {
  43. 			String[] str = in.readLine().split(" ");
  44. 			data[i] = new Data();
  45. 			all_q += data[i].q = parseInt(str[0]);
  46. 			all_r += data[i].r = parseInt(str[1]);
  47. 			data[i].p = (double)data[i].r / (double)data[i].q;
  48. 		}
  49. 		for (; i < 100; i++) {
  50. 			data[i] = new Data();
  51. 		}
  52.  
  53. 		Arrays.sort(data, 0, n);
  54.  
  55. 		int sum_q = 0, sum_r = 0;
  56. 		for (i = 0; sum_q < m && i < n; i++) {
  57. 			sum_q += data[i].q;
  58. 			sum_r += data[i].r;
  59. 		}
  60.  
  61. 		if (n - i > i) {
  62. 			i += 3;
  63. 			foo(m, i > n ? n : i);
  64. 		} else {
  65. 			i -= 5;
  66. 			if (i < 0) {
  67. 				i = 0;
  68. 			}
  69. 			bar(m, n - i, i);
  70. 		}
  71.  
  72. 	}
  73.  
  74. 	static void foo(int m, int n) {
  75. 		int a0, a1, b0, b1, c0;
  76. 		int min, sum_q, sum_r;
  77. 		int i;
  78.  
  79. 		if (n > 25) {
  80. 			b0 = 0;
  81. 			b1 = 1 << (n - 25);
  82. 		} else {
  83. 			b0 = 1 << n;
  84. 			b1 = 0;
  85. 		}
  86.  
  87. 		a0 = 1;
  88. 		a1 = 0;
  89. 		c0 = 1 << 25;
  90. 		min = 250000000;
  91. 		for (;;) {
  92. 			if (a1 > b1) {
  93. 				break;
  94. 			} else if (a1 == b1 && a0 > b0) {
  95. 				break;
  96. 			}
  97. 			if (a0 == c0) {
  98. 				a0 = 0;
  99. 				a1++;
  100. 			}
  101. 			sum_q = sum_r = 0;
  102. 			for (i = 0; i < 25; i++) {
  103. 				if (1 == ((a0 >> i) & 1)) {
  104. 					sum_q += data[i].q;
  105. 					sum_r += data[i].r;
  106. 				}
  107. 				if (1 == ((a1 >> i) & 1)) {
  108. 					sum_q += data[i + 25].q;
  109. 					sum_r += data[i + 25].r;
  110. 				}
  111. 			}
  112. 			if (sum_q >= m && sum_r < min) {
  113. 				min = sum_r;
  114. 			}
  115. 			a0++;
  116. 		}
  117. 		System.out.println(min);
  118. 	}
  119.  
  120. 	static void bar(int m, int n, int d) {
  121. 		int a0, a1, b0, b1, c0;
  122. 		int min, sum_q, sum_r;
  123. 		int i;
  124.  
  125. 		if (n > 25) {
  126. 			b0 = 0;
  127. 			b1 = 1 << (n - 25);
  128. 		} else {
  129. 			b0 = 1 << n;
  130. 			b1 = 0;
  131. 		}
  132.  
  133. 		a0 = 1;
  134. 		a1 = 0;
  135. 		c0 = 1 << 25;
  136. 		min = 250000000;
  137. 		for (;;) {
  138. 			if (a1 > b1) {
  139. 				break;
  140. 			} else if (a1 == b1 && a0 > b0) {
  141. 				break;
  142. 			}
  143. 			if (a0 == c0) {
  144. 				a0 = 0;
  145. 				a1++;
  146. 			}
  147. 			sum_q = sum_r = 0;
  148. 			for (i = 0; i < 25; i++) {
  149. 				if (1 == ((a0 >> i) & 1)) {
  150. 					sum_q += data[i + d].q;
  151. 					sum_r += data[i + d].r;
  152. 				}
  153. 				if (1 == ((a1 >> i) & 1)) {
  154. 					sum_q += data[i + d + 25].q;
  155. 					sum_r += data[i + d + 25].r;
  156. 				}
  157. 			}
  158. 			if (all_q - sum_q >= m && all_r - sum_r < min) {
  159. 				min = all_r - sum_r;
  160. 			}
  161. 			a0++;
  162. 		}
  163. 		System.out.println(min);
  164. 	}
  165.  
  166. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin 
250
5
35 3640
33 2706
98 9810
57 5472
95 7790
stdout 
23072
https://ideone.com/hrxDmb
language:
Java (HotSpot 12)
created:
9 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!