oj.uz

Submission #545892

# Submission time Handle Problem Language Result Execution time Memory
545892 2022-04-05T15:55:51 Z rainboy Ice Hockey World Championship (CEOI15_bobek) C
100 / 100
 49 ms 16696 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 292 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 292 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 0 ms 296 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1748 KB Output is correct
2 Correct 12 ms 4332 KB Output is correct
3 Correct 49 ms 16676 KB Output is correct
4 Correct 13 ms 4400 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2260 KB Output is correct
2 Correct 4 ms 1748 KB Output is correct
3 Correct 10 ms 8404 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 804 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3364 KB Output is correct
2 Correct 14 ms 6448 KB Output is correct
3 Correct 14 ms 6356 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 5 ms 6356 KB Output is correct
6 Correct 16 ms 16696 KB Output is correct
7 Correct 13 ms 6440 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12520 KB Output is correct
2 Correct 4 ms 1828 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 0 ms 288 KB Output is correct
5 Correct 1 ms 808 KB Output is correct
6 Correct 24 ms 12512 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1748 KB Output is correct
2 Correct 10 ms 4408 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 6 ms 6436 KB Output is correct
6 Correct 4 ms 1836 KB Output is correct
7 Correct 34 ms 16624 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16588 KB Output is correct
2 Correct 4 ms 1836 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 40 ms 16572 KB Output is correct
5 Correct 7 ms 8488 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 4 ms 2260 KB Output is correct