fork download 
  1. /* paiza POH! Lite
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/d6d9d6ab6fc49ea6862c73758630e027
  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. } DATA, *PDATA;
  13.  
  14. int m, n;
  15. DATA data[50];
  16.  
  17. int min = 250000000;
  18.  
  19. DATA temp[5][1024];
  20. int s[5];
  21.  
  22. int sort_q(void *a, void *b) {
  23. 	PDATA pa = (PDATA)a;
  24. 	PDATA pb = (PDATA)b;
  25. 	return pb->q - pa->q;
  26. }
  27.  
  28. void foo(int sum_q, int sum_r, int k) {
  29. 	int i, q, r;
  30.  
  31. 	for (i = 0; i < s[k] && temp[k][i].q > 0; i++) {
  32. 		q = sum_q + temp[k][i].q;
  33. 		r = sum_r + temp[k][i].r;
  34. 		if (q >= m) {
  35. 			if (r < min) {
  36. 				min = r;
  37. 			}
  38. 		} else if (k < 4) {
  39. 			foo(q, r, k + 1);
  40. 		} else {
  41. 			return;
  42. 		}
  43. 	}
  44. }
  45.  
  46. int main(void) {
  47. 	int i, j, k, l;
  48.  
  49. 	scanf("%d", &m);
  50. 	scanf("%d", &n);
  51.  
  52. 	for (i = 0; i < n; i++) {
  53. 		scanf("%d %d", &data[i].q, &data[i].r);
  54. 	}
  55. 	qsort(data, n, sizeof(DATA), sort_q);
  56.  
  57. 	for (i = 0; i < 1024; i++) {
  58. 		for (j = 0; j < 10; j++) {
  59. 			if ((i >> j) & 1) {
  60. 				for (k = 0; k < 5; k++) {
  61. 					temp[k][i].q += data[j + k * 10].q;
  62. 					temp[k][i].r += data[j + k * 10].r;
  63. 				}
  64. 			}
  65. 		}
  66.  	}
  67.  
  68. 	for (i = 0; i < 5; i++) {
  69. 		qsort(temp[i], 1024, sizeof(DATA), sort_q);
  70. 	}
  71.  
  72. 	for (i = 0; i < 5; i++) {
  73. 		k = l = 0;
  74. 		for (j = 0; j < 1024; j++) {
  75. 			if (temp[i][j].q == temp[i][k].q) {
  76. 				if (temp[i][j].r < temp[i][k].r) {
  77. 					k = j;
  78. 				}
  79. 			} else {
  80. 				temp[i][l] = temp[i][k];
  81. 				l++;
  82. 				k = j;
  83. 			}
  84. 		}
  85. 		temp[i][l].q = 0;
  86. 		temp[i][l].r = 0;
  87. 		s[i] = l + 1;
  88. 	}
  89.  
  90. 	foo(0, 0, 0);
  91.  
  92. 	printf("%d\n", min);
  93.  
  94. 	return 0;
  95. }
  96.  
Success #stdin #stdout 0s 2424KB
comments (?)
stdin 
250
5
35 3640
33 2706
98 9810
57 5472
95 7790
stdout 
23072
https://ideone.com/FM8Mk6
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!