Submission #544444

#	Time	Username	Problem	Language	Result	Execution time	Memory
544444		rainboy	City (BOI06_city)	C11	100 / 100	8 ms	436 KiB

city

#include <stdio.h>

#define N	20000

long long sum, cnt;

void solve(int *cc, int n, int t, long long cost, int last) {
	int i;

	sum = cnt = 0;
	for (i = 0; i < n; i++)
		if (cost >= cc[i]) {
			long long d = (cost - cc[i]) / t + 1;

			if (d >= 1000000) {
				cnt = 1e13;
				return;
			}
			if (last)
				sum += d * (d + 1) * 2 * cc[i] + (d + 1) * d * (d - 1) / 3 * 4 * t;
			cnt += d * (d + 1) * 2;
		}
}

int main() {
	static int cc[N];
	int n, t, i;
	long long k, lower, upper;

	scanf("%lld%d%d", &k, &t, &n);
	for (i = 0; i < n; i++)
		scanf("%d", &cc[i]);
	lower = 0, upper = 1e18;
	while (upper - lower > 1) {
		long long cost = (lower + upper) / 2;

		solve(cc, n, t, cost, 0);
		if (cnt <= k)
			lower = cost;
		else
			upper = cost;
	}
	solve(cc, n, t, lower, 1);
	printf("%lld\n", sum + (lower + 1) * (k - cnt));
	return 0;
}

Compilation message (stderr)

city.c: In function 'main':
city.c:30:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  scanf("%lld%d%d", &k, &t, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
city.c:32:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d", &cc[i]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100