fork(2) download
copy 
  1. /* paiza POH! Lite
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/35a1b041e3f3b0845bf20927f609d644
  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.  
  36. DATA data[50];
  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.  
  85.  
  86. int main(void) {
  87.  
  88. 	int m, n;
  89. 	PDATA pdata = data;
  90. 	int i, j, k;
  91. 	int sum_q, sum_r;
  92.  
  93. 	scanf("%d", &m);
  94. 	scanf("%d", &n);
  95.  
  96. 	for (i = 0; i < n; i++) {
  97. 		scanf("%d %d", &pdata->q, &pdata->r);
  98. 		pdata->p = (double)pdata->r / (double)pdata->q;
  99. 		pdata++;
  100. 	}
  101.  
  102. 	qsort(data, n, sizeof(DATA), sort_p);
  103.  
  104. 	sum_q = sum_r = 0;
  105. 	pdata = data;
  106. 	for (i = 0; i < n; i++) {
  107. 		sum_q += pdata->q;
  108. 		sum_r += pdata->r;
  109. 		pdata->f = 1;
  110. 		if (sum_q >= m) {
  111. 			break;
  112. 		}
  113. 		pdata++;
  114. 	}
  115.  
  116. 	i += 3;
  117.  
  118. 	foo(m, i > n ? n : i);
  119.  
  120. 	return 0;
  121. }
  122.  
Success #stdin #stdout 0s 2252KB
comments (?)
stdin
copy 
250
5
35 3640
33 2706
98 9810
57 5472
95 7790
stdout
copy 
23072
https://ideone.com/tg9C0f
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!