oj.uz

Submission #784015

# Submission time Handle Problem Language Result Execution time Memory
784015 2023-07-15T14:29:41 Z rainboy Snail (NOI18_snail) C
100 / 100
 2 ms 596 KB 
#include <stdio.h>

#define N	10000
#define INF	0x3f3f3f3f3f3f3f3fLL

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

int main() {
	static long long xx[N + 1], pp[N + 1], qq[N + 1];
	int n, i, i_;
	long long x_, x, k, k_;

	scanf("%lld%d", &x_, &n);
	for (i = 1; i <= n; i++) {
		scanf("%lld", &xx[i]);
		xx[i] += xx[i - 1];
	}
	for (i = 0; i <= n; i++)
		pp[i] = min(i == 0 ? INF : pp[i - 1], xx[i]);
	for (i = n; i >= 0; i--)
		qq[i] = min(i == n ? INF : qq[i + 1], xx[i]);
	k_ = INF, i_ = -1;
	for (i = 1; i <= n; i++) {
		x = xx[i] - pp[i];
		if (x >= x_) {
			k = 0;
			if (k_ > k || k_ == k && i_ > i)
				k_ = k, i_ = i;
		} else if (xx[n] > 0) {
			k = (x_ - x + xx[n] - 1) / xx[n];
			if (k_ > k || k_ == k && i_ > i)
				k_ = k, i_ = i;
		}
		x = xx[i] - qq[i] + xx[n];
		if (x >= x_) {
			k = 1;
			if (k_ > k || k_ == k && i_ > i)
				k_ = k, i_ = i;
		} else if (xx[n] > 0) {
			k = (x_ - x + xx[n] - 1) / xx[n] + 1;
			if (k_ > k || k_ == k && i_ > i)
				k_ = k, i_ = i;
		}
	}
	if (k_ == INF)
		printf("-1 -1\n");
	else
		printf("%lld %d\n", k_, i_ - 1);
	return 0;
}

Compilation message

snail.c: In function 'main':
snail.c:27:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   27 |    if (k_ > k || k_ == k && i_ > i)
      |                  ~~~~~~~~^~~~~~~~~
snail.c:31:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   31 |    if (k_ > k || k_ == k && i_ > i)
      |                  ~~~~~~~~^~~~~~~~~
snail.c:37:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   37 |    if (k_ > k || k_ == k && i_ > i)
      |                  ~~~~~~~~^~~~~~~~~
snail.c:41:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   41 |    if (k_ > k || k_ == k && i_ > i)
      |                  ~~~~~~~~^~~~~~~~~
snail.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%lld%d", &x_, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~
snail.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%lld", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
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 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 428 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 428 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct