fork(1) download 
  1. /* paiza POH! Lite
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/62962df5017c5ed5bb49152bd86a958d
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <time.h>
  9.  
  10. typedef struct _data {
  11. 	int q;
  12. 	int r;
  13. 	double p;
  14. 	int f;
  15. } DATA, *PDATA;
  16.  
  17. int sort_p(void *a, void *b) {
  18. 	PDATA pa = (PDATA)a;
  19. 	PDATA pb = (PDATA)b;
  20. 	double d = pa->p - pb->p;
  21. 	if (d > 0) {
  22. 		return 1;
  23. 	} else if (d < 0) {
  24. 		return -1;
  25. 	} else {
  26. 		return 0;
  27. 	}
  28. }
  29.  
  30. int sort_q(void *a, void *b) {
  31. 	PDATA pa = (PDATA)a;
  32. 	PDATA pb = (PDATA)b;
  33. 	return pb->q - pa->q;
  34. }
  35.  
  36.  
  37. DATA data[50];
  38.  
  39. void foo(int m, int n) {
  40. 	int a0, a1, b0, b1, c0;
  41. 	int min, sum_q, sum_r;
  42. 	int i;
  43.  
  44.  	if (n > 25) {
  45. 		b0 = 0;
  46. 		b1 = 1 << (n - 25);
  47. 	} else {
  48. 		b0 = 1 << n;
  49. 		b1 = 0;
  50. 	}
  51.  
  52. 	a0 = 1;
  53. 	a1 = 0;
  54. 	c0 = 1 << 25;
  55. 	min = 250000000;
  56. 	for (;;) {
  57. 		if (a1 > b1) {
  58. 			break;
  59. 		} else if (a1 == b1 && a0 > b0) {
  60. 			break;
  61. 		}
  62. 		if (a0 == c0) {
  63. 			a0 = 0;
  64. 			a1++;
  65. 		}
  66. 		sum_q = sum_r = 0;
  67. 		for (i = 0; i < 25; i++) {
  68. 			if ((a0 >> i) & 1) {
  69. 				sum_q += data[i].q;
  70. 				sum_r += data[i].r;
  71. 				}
  72. 			if ((a1 >> i) & 1) {
  73. 				sum_q += data[i + 25].q;
  74. 				sum_r += data[i + 25].r;
  75. 			}
  76. 		}
  77. 		if (sum_q >= m && sum_r < min) {
  78. 			min = sum_r;
  79. 		}
  80. 		a0++;
  81. 	}
  82. 	printf("%d\n", min);
  83.  
  84. }
  85.  
  86.  
  87. int main(void) {
  88. 	clock_t tm0, tm1;
  89. 	float dt, lm;
  90.  
  91. 	int m, n;
  92. 	PDATA pdata = data;
  93. 	int i, j, k;
  94. 	int sum_q, sum_r;
  95.  
  96. 	tm0 = clock();
  97.  
  98. 	scanf("%d", &m);
  99. 	scanf("%d", &n);
  100.  
  101. 	for (i = 0; i < n; i++) {
  102. 		scanf("%d %d", &pdata->q, &pdata->r);
  103. 		pdata->p = (double)pdata->r / (double)pdata->q;
  104. 		pdata++;
  105. 	}
  106.  
  107. 	qsort(data, n, sizeof(DATA), sort_p);
  108.  
  109. 	sum_q = sum_r = 0;
  110. 	pdata = data;
  111. 	for (i = 0; i < n; i++) {
  112. 		sum_q += pdata->q;
  113. 		sum_r += pdata->r;
  114. 		pdata->f = 1;
  115. 		if (sum_q >= m) {
  116. 			break;
  117. 		}
  118. 		pdata++;
  119. 	}
  120.  
  121. 	i += 3;
  122.  
  123. 	foo(m, i > n ? n : i);
  124.  
  125.  
  126. 	lm = (double)i;
  127. 	lm /= 100.0;
  128.  
  129. 	do {
  130. 		tm1 = clock() - tm0;
  131. 		dt = ((float)tm1) / CLOCKS_PER_SEC;
  132. 	} while (dt < lm);
  133.  
  134. 	return 0;
  135. }
  136.  
Success #stdin #stdout 0.05s 2296KB
comments (?)
stdin 
250
5
35 3640
33 2706
98 9810
57 5472
95 7790
stdout 
23072
https://ideone.com/1RqhCk
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!