Submission #730940

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
730940	2023-04-26T16:19:41 Z	rainboy	Mountain Trek Route (IZhO12_route)	C	100 / 100	155 ms	21648 KB

route

#include <stdio.h>

#define N	1000000

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

int main() {
	static int aa[N], ii[N], dd[N];
	static long long cc[N + 1];
	int n, k, cnt, i, i_, d, ans;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	i_ = -1;
	for (i = 0; i < n; i++)
		if (i_ == -1 || aa[i_] < aa[i])
			i_ = i;
	cnt = 0;
	for (i = 0; i < n; i++) {
		d = aa[(i_ + i) % n] - aa[(i_ + i + 1) % n];
		if (d > 0)
			ii[cnt] = i, dd[cnt] = d, cnt++;
		else {
			d = -d;
			while (cnt)
				if (d >= dd[cnt - 1])
					cc[i - ii[cnt - 1]] += dd[cnt - 1], d -= dd[cnt - 1], cnt--;
				else {
					cc[i - ii[cnt - 1]] += d, dd[cnt - 1] -= d;
					break;
				}
		}
	}
	ans = 0;
	for (d = 1; d < n; d++)
		if (k / d >= cc[d])
			k -= cc[d] * d, ans += cc[d];
		else {
			ans += k / d;
			break;
		}
	ans *= 2;
	printf("%d\n", ans);
	return 0;
}

Compilation message

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

Subtask #1

100.0 / 100.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	296 KB	Output is correct
5	Correct	0 ms	292 KB	Output is correct
6	Correct	0 ms	292 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	15 ms	2248 KB	Output is correct
11	Correct	15 ms	1704 KB	Output is correct
12	Correct	19 ms	2232 KB	Output is correct
13	Correct	152 ms	21596 KB	Output is correct
14	Correct	150 ms	21648 KB	Output is correct
15	Correct	137 ms	19748 KB	Output is correct
16	Correct	146 ms	20504 KB	Output is correct
17	Correct	155 ms	20512 KB	Output is correct
18	Correct	138 ms	21440 KB	Output is correct
19	Correct	152 ms	21512 KB	Output is correct
20	Correct	120 ms	14000 KB	Output is correct