oj.uz

Submission #440011

# Submission time Handle Problem Language Result Execution time Memory
440011 2021-07-01T12:15:40 Z dongliu0426 Feast (NOI19_feast) C++14
12 / 100
 506 ms 20292 KB 
#include <bits/stdc++.h>
using namespace std;

#define N	300000
#define INF	0x3f3f3f3f3f3f3f3f

int n, k, a[N + 1];
pair<long double, int> dp[N + 1][2];

int main() {
	scanf("%d%d", &n, &k);
	long long sum = 0;
	for (int i = 1; i <= n; ++i)
		scanf("%d", a + i), sum += a[i];
	auto check = [&](long double penalty) {
		dp[0][0] = {0, 0}, dp[0][1] = {-INF, 0};
		for (int i = 1; i <= n; ++i) {
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
			dp[i][1] = max(make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second),
				make_pair(dp[i - 1][0].first + a[i] - penalty, dp[i - 1][0].second + 1));
		}
		return max(dp[n][0], dp[n][1]).second >= k;
	};
	long double lower = 0, upper = sum;
	for (int it = 0; it < 100; ++it) {
		long double mid = (lower + upper) / 2;
		if (check(mid)) {
			lower = mid;
		} else {
			upper = mid;
		}
	}
	long double penalty = lower;
	check(penalty);
	printf("%lld\n", (long long) round(penalty * k + max(dp[n][0], dp[n][1]).first));
}

Compilation message

feast.cpp: In function 'int main()':
feast.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
feast.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d", a + i), sum += a[i];
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 19620 KB Output is correct
2 Correct 451 ms 19992 KB Output is correct
3 Correct 470 ms 20292 KB Output is correct
4 Correct 456 ms 20036 KB Output is correct
5 Correct 464 ms 19872 KB Output is correct
6 Correct 451 ms 19652 KB Output is correct
7 Correct 460 ms 19632 KB Output is correct
8 Correct 471 ms 20032 KB Output is correct
9 Correct 484 ms 19676 KB Output is correct
10 Correct 453 ms 19888 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 19760 KB Output is correct
2 Correct 453 ms 20292 KB Output is correct
3 Correct 440 ms 19648 KB Output is correct
4 Correct 447 ms 19908 KB Output is correct
5 Correct 448 ms 19692 KB Output is correct
6 Correct 432 ms 19708 KB Output is correct
7 Correct 454 ms 20232 KB Output is correct
8 Correct 461 ms 20112 KB Output is correct
9 Correct 445 ms 19524 KB Output is correct
10 Correct 449 ms 20096 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 506 ms 20040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 19620 KB Output is correct
2 Correct 451 ms 19992 KB Output is correct
3 Correct 470 ms 20292 KB Output is correct
4 Correct 456 ms 20036 KB Output is correct
5 Correct 464 ms 19872 KB Output is correct
6 Correct 451 ms 19652 KB Output is correct
7 Correct 460 ms 19632 KB Output is correct
8 Correct 471 ms 20032 KB Output is correct
9 Correct 484 ms 19676 KB Output is correct
10 Correct 453 ms 19888 KB Output is correct
11 Correct 460 ms 19760 KB Output is correct
12 Correct 453 ms 20292 KB Output is correct
13 Correct 440 ms 19648 KB Output is correct
14 Correct 447 ms 19908 KB Output is correct
15 Correct 448 ms 19692 KB Output is correct
16 Correct 432 ms 19708 KB Output is correct
17 Correct 454 ms 20232 KB Output is correct
18 Correct 461 ms 20112 KB Output is correct
19 Correct 445 ms 19524 KB Output is correct
20 Correct 449 ms 20096 KB Output is correct
21 Incorrect 506 ms 20040 KB Output isn't correct
22 Halted 0 ms 0 KB -