Submission #446890

#	Time	Username	Problem	Language	Result	Execution time	Memory
446890		rainboy	Kvalitetni (COCI16_kvalitetni)	C11	12 / 120	2 ms	588 KiB

kvalitetni

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

#define N	1000000
#define K	50
#define Z	50

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

unsigned int X = 12345;

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

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

		while (j < k)
			if (aa[j] == a)
				j++;
			else if (aa[j] < a) {
				tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
			}
		sort(aa, l, i);
		l = k;
	}
}

char cc[N + 1]; int zz[K + 1];

int solve_(char *cc, int n, int *j_) {
	int i, j, k, sum, prod, add;

	if (cc[1] == '?') {
		*j_ = 3;
		return zz[1];
	} else {
		sum = 0, prod = 1, add = -1;
		for (i = 1, k = 0; i < n && cc[i] == '('; i += j + 1, k++) {
			int x = solve_(cc + i, n - i, &j);

			if (add == -1)
				add = cc[j] == '+';
			sum = min(sum + x, Z), prod = min(prod * x, Z);
		}
		*j_ = i;
		return min(add ? sum : prod, zz[k]);
	}
}

double solve(char *cc, int n) {
	static int aa[K];
	int h, i, j, k, add, sum;
	double prod;

	add = -1;
	for (i = 1, k = 0; i < n && cc[i] == '('; i += j + 1) {
		aa[k++] = solve_(cc + i, n - i, &j);
		if (add == -1)
			add = cc[i + j] == '+';
	}
	if (k == 1)
		return aa[0];
	else if (add == 1) {
		sum = 0;
		for (h = 0; h < k; h++)
			sum += aa[h];
		return min(sum, zz[k]);
	} else {
		sort(aa, 0, k);
		sum = 0, prod = 1;
		for (h = 0; h < k; h++) {
			if (sum + aa[h] * (k - h) >= zz[k]) {
				double a = (double) (zz[k] - sum) / (k - h);

				while (h < k)
					prod *= a, h++;
				return prod;
			}
			sum += aa[h], prod *= aa[h];
		}
		return prod;
	}
}

int main() {
	int n, k, h;

	scanf("%d", &k);
	for (h = 1; h <= k; h++)
		scanf("%d", &zz[h]);
	scanf("%s", cc), n = strlen(cc);
	printf("%f\n", solve(cc, n));
	return 0;
}

Compilation message (stderr)

kvalitetni.c: In function 'main':
kvalitetni.c:95:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  scanf("%d", &k);
      |  ^~~~~~~~~~~~~~~
kvalitetni.c:97:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   scanf("%d", &zz[h]);
      |   ^~~~~~~~~~~~~~~~~~~
kvalitetni.c:98:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |  scanf("%s", cc), n = strlen(cc);
      |  ^~~~~~~~~~~~~~~

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