oj.uz

Submission #471229

# Submission time Handle Problem Language Result Execution time Memory
471229 2021-09-07T17:43:02 Z rainboy San (COCI17_san) C
120 / 120
 62 ms 19500 KB 
#include <stdio.h>

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

int first[1 << M], last[1 << M];

void init() {
	int i, b;

	for (b = 1; b < 1 << M; b++) {
		i = 0;
		while ((b & 1 << i) == 0)
			i++;
		first[b] = i;
		i = M - 1;
		while ((b & 1 << i) == 0)
			i--;
		last[b] = i;
	}
}

void merge(long long *ww, int *uu, int n, int *vv, int m) {
	int i = n - 1, j = m - 1, k = n + m - 1;

	while (i >= 0 && j >= 0)
		uu[k--] = ww[uu[i]] > ww[vv[j]] ? uu[i--] : vv[j--];
	while (i >= 0)
		uu[k--] = uu[i--];
	while (j >= 0)
		uu[k--] = vv[j--];
}

int main() {
	static int aa[N], bb[N], uu[1 << M], uu_[1 << M], vv[1 << M], vv_[1 << M], kk[M];
	static long long ww[1 << M], xx[1 << M];
	int n, m, h, h1, h2, i, k1, k1_, k2, k2_, u, v;
	long long l, ans;

	init();
	scanf("%d%lld", &n, &l), m = n / 2;
	for (i = 0; i < n; i++)
		scanf("%d%d", &aa[i], &bb[i]);
	k1 = 0;
	uu[k1++] = 0;
	for (i = 0; i < m; i++) {
		k1_ = 0;
		for (h = 0; h < k1; h++) {
			u = uu[h];
			if (u == 0 || aa[last[u]] <= aa[i])
				ww[uu_[k1_++] = u | 1 << i] = ww[u] + bb[i];
		}
		merge(ww, uu, k1, uu_, k1_), k1 += k1_;
	}
	k2 = 0;
	vv[k2++] = 0;
	for (i = m; i < n; i++) {
		k2_ = 0;
		for (h = 0; h < k2; h++) {
			v = vv[h];
			if (v == 0 || aa[m + last[v]] <= aa[i])
				xx[vv_[k2_++] = v | 1 << i - m] = xx[v] + bb[i];
		}
		merge(xx, vv, k2, vv_, k2_), k2 += k2_;
	}
	ans = 0;
	for (h1 = 0; h1 < k1; h1++)
		if (ww[uu[h1]] >= l)
			ans++;
	for (h2 = 0; h2 < k2; h2++)
		if (xx[vv[h2]] >= l)
			ans++;
	for (h1 = 0, h2 = k2 - 1; h1 < k1; h1++) {
		u = uu[h1];
		while (h2 >= 0 && ww[u] + xx[vv[h2]] >= l) {
			if (vv[h2] > 0)
				kk[first[vv[h2]]]++;
			h2--;
		}
		if (u > 0)
			for (i = m; i < n; i++)
				if (aa[last[u]] <= aa[i])
					ans += kk[i - m];
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

san.c: In function 'main':
san.c:62:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   62 |     xx[vv_[k2_++] = v | 1 << i - m] = xx[v] + bb[i];
      |                              ~~^~~
san.c:41:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%lld", &n, &l), m = n / 2;
      |  ^~~~~~~~~~~~~~~~~~~~~~~
san.c:43:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d", &aa[i], &bb[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8524 KB Output is correct
2 Correct 7 ms 8524 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8524 KB Output is correct
2 Correct 7 ms 8524 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9804 KB Output is correct
2 Correct 7 ms 8908 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12320 KB Output is correct
2 Correct 10 ms 11468 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 19500 KB Output is correct
2 Correct 17 ms 11692 KB Output is correct