fork download 
  1. /* paiza POH! Vol.1
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/ec-campaign/result/4935ad2d41c086e6f41b61bdf324c844
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #define DFSIZE (5)
  9.  
  10. int price[1000000] = {0};
  11. int list[500000];
  12.  
  13. inline int getInt(void) {
  14. 	register int c, n = 0;
  15. 	do {
  16. 		c = getchar();
  17. 	} while ((c < '0') || (c > '9'));
  18. 	do {
  19. 		n = n * 10 + (c - '0');
  20. 		c = getchar();
  21. 	} while ((c >= '0') && (c <= '9'));
  22. 	return n;
  23. }
  24.  
  25. void putInt(register int n) {
  26. 	register int t;
  27. 	if (n < 10) {
  28. 		putchar(n + '0');
  29. 	} else {
  30. 		t = n / 10;
  31. 		putInt(t);
  32. 		putchar(n - t * 10 + '0');
  33. 	}
  34. }
  35.  
  36. int foo(const int *p, const int f, const int e, const int m) {
  37. 	int ci, df = e - f;
  38. 	if (df < DFSIZE) return e;
  39. 	if (m < p[ci = (f + (df >> 1))]) {
  40. 		return foo(p, f, ci, m);
  41. 	} else {
  42. 		return foo(p, ci, e, m);
  43. 	}
  44. }
  45.  
  46. int bar(const int *p, const int f, const int e, const int m) {
  47. 	int ci, df = e - f;
  48. 	if (df < DFSIZE) return f;
  49. 	if (m > p[ci = (f + (df >> 1))]) {
  50. 		return bar(p, ci, e, m);
  51. 	} else {
  52. 		return bar(p, f, ci, m);
  53. 	}
  54. }
  55.  
  56. int main(void) {
  57. 	register int j, *f, *e, sum, tmp;
  58. 	int n, d, m, p, fi, i, df;
  59.  
  60. 	n = getInt();
  61. 	d = getInt();
  62.  
  63. 	j = n + 1;
  64. 	while (--j) {
  65. 		++price[getInt()];
  66. 	}
  67.  
  68. 	/* sort */
  69. 	j = 0;
  70. 	i = 10;
  71. 	do {
  72. 		while (!price[i]) ++i;
  73. 		--price[i];
  74. 		list[j] = i;
  75. 		++j;
  76. 	} while (j < n);
  77.  
  78. 	--n;
  79. 	j = d + 1;
  80. 	while (--j) {
  81. 		m = getInt();
  82. 		tmp = 0;
  83. 		f = list + (fi = foo(list, 0, n, m));
  84. 		while (*f >= m) --f;
  85. 		if ((df = m - *f) <= *f) {
  86. 			e = list + bar(list, 0, fi, df);
  87. 			do {
  88. 				while (df > *e) ++e;
  89. 				if (((df < *e) || (f == e)) && (e != list)) --e;
  90. 				if (((sum = *f + *e) > tmp) && (sum <= m)) {
  91. 					if ((tmp = sum) == m) break;
  92. 				}
  93. 				--f;
  94. 			} while ((df = m - *f) <= *f);
  95. 		}
  96. 		putInt(tmp);
  97. 		putchar('\n');
  98. 	}
  99. 	return 0;
  100. }
  101.  
  102.  
Success #stdin #stdout 0s 8108KB
comments (?)
stdin 
    10 6
    4500
   13300
    1100
    2200
   25100
    4000
    3000
    1000
    2000
    5000
    10000
    3000
    15000
    30000
    4000
    5600
stdout 
9500
3000
14400
29600
4000
5600
https://ideone.com/i0qaS0
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!