Submission #544749

#	Time	Username	Problem	Language	Result	Execution time	Memory
544749		rainboy	Olympiads (BOI19_olympiads)	C11	100 / 100	42 ms	360 KiB

olympiads

#include <stdio.h>
#include <string.h>

#define N	500
#define K	6
#define C	2000

int min(int a, int b) { return a < b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *aa_;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa_[ii[j]] == aa_[i_])
				j++;
			else if (aa_[ii[j]] > aa_[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int aa[K][N], ii[K][N], ch[N + 1][K + 1], n, k, c, s_, cnt; char type[N];

int best() {
	int h, i, s = 0;

	for (h = 0; h < k; h++)
		for (i = 0; i < n; i++)
			if (type[ii[h][i]]) {
				s += aa[h][ii[h][i]];
				break;
			}
	return s;
}

int solve(int h, int i, int n_, int k_) {
	int i_;

	if (n_ < k || i == n || best() < s_)
		return 0;
	if (h == k)
		return (cnt += ch[n_ - k_][k - k_]) >= c;
	i_ = ii[h][i];
	if (type[i_] == 0) {
		if (solve(h, i + 1, n_, k_))
			return 1;
	} else if (type[i_] == 1) {
		type[i_] = 2;
		if (solve(h + 1, 0, n_, k_ + 1))
			return 1;
		type[i_] = 0;
		if (solve(h, i + 1, n_ - 1, k_))
			return 1;
		type[i_] = 1;
	} else if (type[i_] == 2) {
		if (solve(h + 1, 0, n_, k_))
			return 1;
	}
	return 0;
}

int main() {
	int h, i, j, lower, upper;

	scanf("%d%d%d", &n, &k, &c);
	for (i = 0; i < n; i++)
		for (h = 0; h < k; h++)
			scanf("%d", &aa[h][i]);
	for (h = 0; h < k; h++) {
		for (i = 0; i < n; i++)
			ii[h][i] = i;
		aa_ = aa[h], sort(ii[h], 0, n);
	}
	ch[0][0] = 1;
	for (i = 1; i <= n; i++) {
		ch[i][0] = 1;
		for (j = 1; j <= i && j <= k; j++)
			ch[i][j] = min(ch[i - 1][j] + ch[i - 1][j - 1], C);
	}
	lower = 0, upper = 500000001;
	while (upper - lower > 1) {
		s_ = (lower + upper) / 2;
		memset(type, 1, n * sizeof *type);
		cnt = 0;
		if (solve(0, 0, n, 0))
			lower = s_;
		else
			upper = s_;
	}
	printf("%d\n", lower);
	return 0;
}

Compilation message (stderr)

olympiads.c: In function 'main':
olympiads.c:80:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%d%d", &n, &k, &c);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
olympiads.c:83:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |    scanf("%d", &aa[h][i]);
      |    ^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32