oj.uz

Submission #446903

# Submission time Handle Problem Language Result Execution time Memory
446903 2021-07-23T18:06:36 Z rainboy Kvalitetni (COCI16_kvalitetni) C
120 / 120
 3 ms 972 KB 
#include <stdio.h>
#include <string.h>

#define N	1000000
#define K	50

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

unsigned int X = 12345;

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

void sort(double *aa, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r;
		double 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];

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

	if (cc[1] == '?') {
		*j_ = 3;
		return zz[1];
	}
	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] == '+';
	}
	*j_ = i;
	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("%.6f\n", solve(cc, n, &h));
	return 0;
}

Compilation message

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 588 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 716 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 972 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 588 KB Output is correct