oj.uz

Submission #722771

# Submission time Handle Problem Language Result Execution time Memory
722771 2023-04-12T20:19:51 Z rainboy Card Scoring (CCO19_day2problem1) C++17
25 / 100
 4867 ms 96992 KB 
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define N	1000000

int *xx[N]; double *yy[N]; int cnt[N], cnt_[N], xx_[N], n; double k;

int crossover(int x1, double y1, int x2, double y2) {
	int lower = x2, upper = n + 1;

	while (upper - lower > 1) {
		int x = (lower + upper) / 2;

		if (y1 + pow(x - x1, k) >= y2 + pow(x - x2, k))
			upper = x;
		else
			lower = x;
	}
	return upper;
}

void add(int a, double y) {
	while (cnt[a] && crossover(xx[a][cnt[a] - 2], yy[a][cnt[a] - 2], xx[a][cnt[a] - 1], yy[a][cnt[a] - 1]) <= crossover(xx[a][cnt[a] - 1], yy[a][cnt[a] - 1], xx_[a], y))
		cnt[a]--;
	if (cnt[a] == cnt_[a]) {
		xx[a] = (int *) realloc(xx[a], cnt_[a] * 2 * sizeof *xx[a]);
		yy[a] = (double *) realloc(yy[a], cnt_[a] * 2 * sizeof *yy[a]);
		cnt_[a] *= 2;
	}
	xx[a][cnt[a]] = xx_[a], yy[a][cnt[a]] = y, cnt[a]++;
	xx_[a]++;
}

int main() {
	int i, a;
	double y;

	scanf("%lf%d", &k, &n), k /= 2;
	for (a = 0; a < n; a++) {
		xx[a] = (int *) malloc((cnt_[a] = 2) * sizeof *xx[a]);
		yy[a] = (double *) malloc((cnt_[a] = 2) * sizeof *yy[a]);
	}
	y = 0;
	for (i = 0; i < n; i++) {
		scanf("%d", &a), a--;
		add(a, y);
		while (cnt[a] && yy[a][cnt[a] - 1] + pow(xx_[a] - xx[a][cnt[a] - 1], k) <= yy[a][cnt[a] - 2] + pow(xx_[a] - xx[a][cnt[a] - 2], k))
			cnt[a]--;
		y = yy[a][cnt[a] - 1] + pow(xx_[a] - xx[a][cnt[a] - 1], k);
	}
	printf("%.9f\n", y);
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%lf%d", &k, &n), k /= 2;
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%d", &a), a--;
      |   ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 12 ms 660 KB Output is correct
11 Correct 16 ms 684 KB Output is correct
12 Correct 8 ms 596 KB Output is correct
13 Correct 8 ms 724 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3918 ms 84400 KB Output is correct
2 Correct 4668 ms 85288 KB Output is correct
3 Correct 1176 ms 42288 KB Output is correct
4 Correct 2311 ms 43488 KB Output is correct
5 Correct 1272 ms 94680 KB Output is correct
6 Correct 2528 ms 91504 KB Output is correct
7 Correct 2454 ms 91564 KB Output is correct
8 Correct 2500 ms 91480 KB Output is correct
9 Correct 2516 ms 91472 KB Output is correct
10 Correct 2518 ms 91472 KB Output is correct
11 Correct 2399 ms 85148 KB Output is correct
12 Correct 2442 ms 86232 KB Output is correct
13 Correct 2231 ms 84436 KB Output is correct
14 Correct 4741 ms 86560 KB Output is correct
15 Correct 4867 ms 86448 KB Output is correct
16 Correct 4715 ms 86472 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 12 ms 660 KB Output is correct
19 Correct 16 ms 684 KB Output is correct
20 Correct 8 ms 596 KB Output is correct
21 Correct 8 ms 724 KB Output is correct
22 Correct 3918 ms 84400 KB Output is correct
23 Correct 4668 ms 85288 KB Output is correct
24 Correct 1176 ms 42288 KB Output is correct
25 Correct 2311 ms 43488 KB Output is correct
26 Correct 1272 ms 94680 KB Output is correct
27 Correct 2528 ms 91504 KB Output is correct
28 Correct 2454 ms 91564 KB Output is correct
29 Correct 2500 ms 91480 KB Output is correct
30 Correct 2516 ms 91472 KB Output is correct
31 Correct 2518 ms 91472 KB Output is correct
32 Correct 2399 ms 85148 KB Output is correct
33 Correct 2442 ms 86232 KB Output is correct
34 Correct 2231 ms 84436 KB Output is correct
35 Correct 4741 ms 86560 KB Output is correct
36 Correct 4867 ms 86448 KB Output is correct
37 Correct 4715 ms 86472 KB Output is correct
38 Correct 1339 ms 96992 KB Output is correct
39 Correct 4124 ms 84508 KB Output is correct
40 Correct 4801 ms 85304 KB Output is correct
41 Correct 1184 ms 42384 KB Output is correct
42 Correct 2312 ms 43484 KB Output is correct
43 Correct 1310 ms 94736 KB Output is correct
44 Correct 2479 ms 91544 KB Output is correct
45 Correct 2468 ms 86136 KB Output is correct
46 Correct 2481 ms 85240 KB Output is correct
47 Correct 2231 ms 84376 KB Output is correct
48 Correct 4864 ms 85360 KB Output is correct
49 Correct 4865 ms 85704 KB Output is correct
50 Correct 4687 ms 85668 KB Output is correct