fork(1) download
copy 
  1. /* paiza POH! Lite
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/fcb6a30d5dfc8e0fd781c5ed4efc1b6a
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8.  
  9. typedef struct _data {
  10. 	int q;
  11. 	int r;
  12. 	double p;
  13. 	int f;
  14. } DATA, *PDATA;
  15.  
  16. int sort_p(void *a, void *b) {
  17. 	PDATA pa = (PDATA)a;
  18. 	PDATA pb = (PDATA)b;
  19. 	double d = pa->p - pb->p;
  20. 	if (d > 0) {
  21. 		return 1;
  22. 	} else if (d < 0) {
  23. 		return -1;
  24. 	} else {
  25. 		return 0;
  26. 	}
  27. }
  28.  
  29. int sort_q(void *a, void *b) {
  30. 	PDATA pa = (PDATA)a;
  31. 	PDATA pb = (PDATA)b;
  32. 	return pb->q - pa->q;
  33. }
  34.  
  35. int all_q, all_r;
  36. DATA data[100];
  37.  
  38. void foo(int m, int n) {
  39. 	int a0, a1, b0, b1, c0;
  40. 	int min, sum_q, sum_r;
  41. 	int i;
  42.  
  43.  	if (n > 25) {
  44. 		b0 = 0;
  45. 		b1 = 1 << (n - 25);
  46. 	} else {
  47. 		b0 = 1 << n;
  48. 		b1 = 0;
  49. 	}
  50.  
  51. 	a0 = 1;
  52. 	a1 = 0;
  53. 	c0 = 1 << 25;
  54. 	min = 250000000;
  55. 	for (;;) {
  56. 		if (a1 > b1) {
  57. 			break;
  58. 		} else if (a1 == b1 && a0 > b0) {
  59. 			break;
  60. 		}
  61. 		if (a0 == c0) {
  62. 			a0 = 0;
  63. 			a1++;
  64. 		}
  65. 		sum_q = sum_r = 0;
  66. 		for (i = 0; i < 25; i++) {
  67. 			if ((a0 >> i) & 1) {
  68. 				sum_q += data[i].q;
  69. 				sum_r += data[i].r;
  70. 				}
  71. 			if ((a1 >> i) & 1) {
  72. 				sum_q += data[i + 25].q;
  73. 				sum_r += data[i + 25].r;
  74. 			}
  75. 		}
  76. 		if (sum_q >= m && sum_r < min) {
  77. 			min = sum_r;
  78. 		}
  79. 		a0++;
  80. 	}
  81. 	printf("%d\n", min);
  82. }
  83.  
  84. void bar(int m, int n, int d) {
  85. 	int a0, a1, b0, b1, c0;
  86. 	int min, sum_q, sum_r;
  87. 	int i;
  88.  
  89.  	if (n > 25) {
  90. 		b0 = 0;
  91. 		b1 = 1 << (n - 25);
  92. 	} else {
  93. 		b0 = 1 << n;
  94. 		b1 = 0;
  95. 	}
  96.  
  97. 	a0 = 1;
  98. 	a1 = 0;
  99. 	c0 = 1 << 25;
  100. 	min = 250000000;
  101. 	for (;;) {
  102. 		if (a1 > b1) {
  103. 			break;
  104. 		} else if (a1 == b1 && a0 > b0) {
  105. 			break;
  106. 		}
  107. 		if (a0 == c0) {
  108. 			a0 = 0;
  109. 			a1++;
  110. 		}
  111. 		sum_q = sum_r = 0;
  112. 		for (i = 0; i < 25; i++) {
  113. 			if ((a0 >> i) & 1) {
  114. 				sum_q += data[i + d].q;
  115. 				sum_r += data[i + d].r;
  116. 				}
  117. 			if ((a1 >> i) & 1) {
  118. 				sum_q += data[i + d + 25].q;
  119. 				sum_r += data[i + d + 25].r;
  120. 			}
  121. 		}
  122. 		if (all_q - sum_q >= m && all_r - sum_r < min) {
  123. 			min = all_r - sum_r;
  124. 		}
  125. 		a0++;
  126. 	}
  127. 	printf("%d\n", min);
  128. }
  129.  
  130.  
  131. int main(void) {
  132.  
  133. 	int m, n;
  134. 	PDATA pdata = data;
  135. 	int i, j, k;
  136. 	int sum_q, sum_r;
  137.  
  138. 	scanf("%d", &m);
  139. 	scanf("%d", &n);
  140.  
  141. 	for (i = 0; i < n; i++) {
  142. 		scanf("%d %d", &pdata->q, &pdata->r);
  143. 		all_q += pdata->q;
  144. 		all_r += pdata->r;
  145. 		pdata->p = (double)pdata->r / (double)pdata->q;
  146. 		pdata++;
  147. 	}
  148.  
  149. 	qsort(data, n, sizeof(DATA), sort_p);
  150.  
  151. 	sum_q = sum_r = 0;
  152. 	pdata = data;
  153. 	for (i = 0; i < n; i++) {
  154. 		sum_q += pdata->q;
  155. 		sum_r += pdata->r;
  156. 		pdata->f = 1;
  157. 		if (sum_q >= m) {
  158. 			break;
  159. 		}
  160. 		pdata++;
  161. 	}
  162.  
  163. 	if (n - i > i) {
  164. 		i += 3;
  165. 		foo(m, i > n ? n : i);
  166. 	} else {
  167. 		i -= 5;
  168. 		if (i < 0) {
  169. 			i = 0;
  170. 		}
  171. 		bar(m, n - i, i);	
  172. 	}
  173.  
  174. 	return 0;
  175. }
  176.  
Success #stdin #stdout 0s 2296KB
comments (?)
stdin
copy 
250
5
35 3640
33 2706
98 9810
57 5472
95 7790
stdout
copy 
23072
https://ideone.com/Ah3BFj
language:
C (gcc 8.3)
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!