Submission #730940

#	Time	Username	Problem	Language	Result	Execution time	Memory
730940		rainboy	Mountain Trek Route (IZhO12_route)	C11	100 / 100	155 ms	21648 KiB

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 (stderr)

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 / 100