fork(1) download
copy 
  1. /* paiza POH! Lite
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/c280a18433b821b893a3b592f7bfa356
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8.  
  9. /* 全通りの組み合わせから条件に符合する答えを求める */
  10. #define SEEK(I, Q, R)                         \
  11. 	{                                         \
  12. 		b = 1LL << nn;                        \
  13. 		for (;;) {                            \
  14. 			if (a > b) {                      \
  15. 				break;                        \
  16. 			}                                 \
  17. 			sum_q = sum_r = 0;                \
  18. 			for (i = 0; i < n; i++) {         \
  19. 				if ((a >> i) & 1LL) {         \
  20. 					sum_q += data[(I)].q;     \
  21. 					sum_r += data[(I)].r;     \
  22. 				}                             \
  23. 			}                                 \
  24. 			if (((Q) >= m) && ((R) < min)) {  \
  25. 				min = (R);                    \
  26. 			}                                 \
  27. 			a++;                              \
  28. 		}                                     \
  29. 	}
  30.  
  31.  
  32. /* 1社ごとの情報 */
  33. typedef struct _data {
  34. 	int q; /* 動員人数 */
  35. 	int r; /* 費用 */
  36. 	double p; /* 1人あたりの人件費 */
  37. } DATA, *PDATA;
  38.  
  39. /* 1人あたりの人件費を昇順(安い順)でソート */
  40. int sort_p(void *a, void *b) {
  41. 	PDATA pa = (PDATA)a;
  42. 	PDATA pb = (PDATA)b;
  43. 	double d = pa->p - pb->p;
  44. 	if (d > 0) {
  45. 		return 1;
  46. 	} else if (d < 0) {
  47. 		return -1;
  48. 	} else {
  49. 		return 0;
  50. 	}
  51. }
  52.  
  53. int main(void) {
  54.  
  55. 	int m; /* 必要な人数 */
  56. 	int n; /* 会社の数 */
  57. 	DATA data[50]; /* 全n社の各社の人数と費用 */
  58.  
  59. 	PDATA pdata;
  60. 	int i;
  61.  
  62. 	int all_q = 0; /* 全n社の人数の合計 */
  63. 	int all_r = 0; /* 全n社の費用の合計 */
  64.  
  65. 	int sum_q, sum_r, min, d, nn;
  66. 	long long a, b;
  67.  
  68. 	scanf("%d", &m);
  69. 	scanf("%d", &n);
  70.  
  71. 	pdata = data;
  72. 	for (i = 0; i < n; i++) {
  73. 		scanf("%d %d", &pdata->q, &pdata->r);
  74. 		pdata->p = (double)pdata->r / (double)pdata->q;
  75. 		all_q += pdata->q;
  76. 		all_r += pdata->r;
  77. 		pdata++;
  78. 	}
  79.  
  80. 	qsort(data, n, sizeof(DATA), sort_p);
  81.  
  82. 	/* 人件費の割安な会社から順に人数を合計し */
  83. 	/* 合計人数が初めてm以上になる位置を求める */
  84. 	sum_q = sum_r = 0;
  85. 	pdata = data;
  86. 	for (i = 0; i < n; i++) {
  87. 		sum_q += pdata->q;
  88. 		sum_r += pdata->r;
  89. 		if (sum_q >= m) {
  90. 			break;
  91. 		}
  92. 		pdata++;
  93. 	}
  94.  
  95. 	min = 250000000;
  96. 	a = 1LL;
  97.  
  98. 	if (n - i > i) {
  99. 		/* 求めた割安な会社数が全n社の半分より少ないとき */
  100. 		/* 割安な会社をさらに3社追加し */
  101. 		/* 割高な会社は絶対使わないだろうと決め付け */
  102. 		/* その中で全通りの組み合わせを求め 条件に符号する結果を得る */
  103. 		d = i + 3;
  104. 		nn = d > n ? n : d;
  105. 		SEEK(i, sum_q, sum_r);
  106. 	} else {
  107. 		/* 求めた割安な会社数が全n社の半分より多いとき */
  108. 		/* 前者とは逆に使わない割高の会社の組み合わせから結果を求める */
  109. 		/* 求めた割安な会社数から5社を除いた会社を絶対使うだろうと決め付け */
  110. 		/* 割高な会社で全通りの組み合わせを求め 条件に符号する結果を得る */
  111. 		d = i - 5;
  112. 		if (d < 0) {
  113. 			d = 0;
  114. 		}
  115. 		nn = n - d;
  116. 		SEEK(i + d, all_q - sum_q, all_r - sum_r);
  117. 	}
  118.  
  119. 	printf("%d\n", min);
  120.  
  121. 	return 0;
  122. }
  123.  
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/nU8MX3
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!