fork(2) download 
  1. /* paiza POH! Vol.1
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/ec-campaign/result/3999135a6325fb8b1b6a3b282512e299
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8.  
  9. /* 商品の最大価格 */
  10. #define PMAX (1000000)
  11.  
  12. /* 商品の価格ごとの個数を格納する */
  13. int list[PMAX + 1] = {1,1,1,1,1, 1,1,1,1,1};
  14.  
  15. /* putInt()用 */
  16. char str[10] = {'\n'};
  17.  
  18. /* scanf("%d", &n) が遅い気がするから代わりに */
  19. inline int getInt(void) {
  20.     int c, n = 0;
  21.     do {
  22.         c = getchar();
  23.     } while ((c < '0') || (c > '9'));
  24.     do {
  25.         n = n * 10 + (c - '0');
  26.         c = getchar();
  27.     } while ((c >= '0') && (c <= '9'));
  28.     return n;
  29. }
  30.  
  31. /* printf("%d\n", n)が遅い気がするから代わりに */
  32. inline void putInt(int n) {
  33. 	int t, i = 1;
  34. 	do {
  35. 		t = n / 10;
  36. 		str[i] = n - t * 10 + '0';
  37. 		++i; n = t;
  38. 	} while (n > 0);
  39. 	do {
  40. 		putchar(str[--i]);
  41. 	} while (i);
  42. }
  43.  
  44. int main(void) {
  45.     int i, u, tmp, n, d, m;
  46.  
  47.     n = getInt(); /* 商品の数          	*/
  48.     d = getInt(); /* キャンペーンの日数	*/
  49.  
  50.     /* 商品の価格ごとの個数を数える */
  51.     do {
  52.         ++list[getInt()];
  53.     } while (--n);
  54.  
  55.     /* アルゴリズム
  56.      * 例えばキャンペーン上限が 10000 だとしたら
  57.      * (A) 9999から存在する商品を見つける 
  58.      *   (例えば 9999～9801 まで商品が なく 9800 で初めて見つかるなど)
  59.      * (B) 次に 200 (= 10000 - 9800) から存在する価格を見つける 
  60.      *   (例えば 200～121 まで商品がなく 120 で初めて商品を見つかるなど)
  61.      * (C) ここで 9800 + 120 = 9920 を見つけた合計値とし
  62.      *   それまでに見つけた最大値と比較、上限値に達した場合はループを抜ける
  63.      * 次に 9799 から同様に(A)～(C)の手順を繰り返して探していく
  64.      */
  65.     do {
  66.     	/* キャンペーン上限の取得 */
  67.         i = m = getInt();
  68.  
  69.         /* 見つけた最大値を保持する(見つからなかった場合の0で初期化) */
  70.         tmp = 0; 
  71.  
  72. 		do {
  73. 			 /* (A)の大きい側の価格の商品を見つける */
  74. 			--i;
  75. 			while(!list[i]) --i;
  76.  
  77. 			/* (B)の探索開始の価格を決める	*/
  78. 			/* (A)と(B)が逆転したら探索終了 */
  79. 			if ((u = m - i) > i) break; 
  80.  
  81. 			/* (A)と(B)が同じ価格の場合、            	*/
  82. 			/* 商品が2個以上なければ(B)の開始値を下げる */
  83. 			if ((i == u) && (list[i] < 2)) --u;
  84.  
  85. 			/* (B)の小さい側の価格の商品を見つける */
  86. 			while (!list[u]) --u; 
  87.  
  88. 			/* 合計値(u += i)、最大値tmp、上限値m                         	*/
  89. 			/* 最大値の更新および、上限値に達した場合の探索終了(ループ抜け) */
  90. 			if ((u > 9) && ((u += i) > tmp) && ((tmp = u) == m)) break;
  91.  
  92.         } while (1);
  93.  
  94.         /* 結果の表示 */
  95.         putInt(tmp);
  96.  
  97.     } while (--d);
  98.  
  99.     return 0;
  100. }
  101.  
  102.  
Success #stdin #stdout 0s 6156KB
comments (?)
stdin 
    5 2
    4000
    3000
    1000
    2000
    5000
    10000
    3000
stdout 
9000
3000
https://ideone.com/fiXbui
language:
C (gcc 8.3)
created:
10 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!