Submission #545892

#	Time	Username	Problem	Language	Result	Execution time	Memory
545892		rainboy	Ice Hockey World Championship (CEOI15_bobek)	C11	100 / 100	49 ms	16696 KiB

bobek

#include <stdio.h>

#define N	40
#define N_	(N / 2)

void solve(long long *aa, long long *ss, int n) {
	int m, h, h1, h2, i;

	for (i = 0; i < n; i++) {
		m = 1 << i, h = m * 2 - 1, h1 = m - 1, h2 = m - 1;
		while (h1 >= 0 && h2 >= 0)
			ss[h--] = ss[h1] > ss[h2] + aa[i] ? ss[h1--] : ss[h2--] + aa[i];
	}
}

int main() {
	static long long aa[N], ss[1 << N_], tt[1 << N_];
	int n, i, m1, m2, h1, h2;
	long long s, ans;

	scanf("%d%lld", &n, &s);
	for (i = 0; i < n; i++)
		scanf("%lld", &aa[i]);
	solve(aa, ss, n / 2), solve(aa + n / 2, tt, n - n / 2);
	m1 = 1 << n / 2, m2 = 1 << n - n / 2;
	ans = 0;
	for (h1 = 0, h2 = m2 - 1; h1 < m1; h1++) {
		while (h2 >= 0 && ss[h1] + tt[h2] > s)
			h2--;
		ans += h2 + 1;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

bobek.c: In function 'main':
bobek.c:25:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   25 |  m1 = 1 << n / 2, m2 = 1 << n - n / 2;
      |                             ~~^~~~~~~
bobek.c:21:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d%lld", &n, &s);
      |  ^~~~~~~~~~~~~~~~~~~~~~~
bobek.c:23:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%lld", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10