oj.uz

Submission #544444

# Submission time Handle Problem Language Result Execution time Memory
544444 2022-04-01T23:41:38 Z rainboy City (BOI06_city) C
100 / 100
 8 ms 436 KB 
#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

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.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 2 ms 308 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 8 ms 436 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct