oj.uz

Submission #440783

# Submission time Handle Problem Language Result Execution time Memory
440783 2021-07-03T02:04:59 Z dongliu0426 Feast (NOI19_feast) C++14
63 / 100
 1000 ms 23260 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 300000;
const long long INF = (long long) 300000 * 1000000000;
const long double EPS = 1e-6;

int n, k, a[N + 1];
pair<long double, int> dp[N + 1][2];
	
bool 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;
};

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i)
		scanf("%d", a + i);
	long double lower = 0, upper = INF;
	while (lower + EPS < upper) {
		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:24:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
feast.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d", a + i);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 22340 KB Output is correct
2 Correct 383 ms 22848 KB Output is correct
3 Correct 410 ms 23096 KB Output is correct
4 Correct 414 ms 22940 KB Output is correct
5 Correct 367 ms 22824 KB Output is correct
6 Correct 388 ms 22440 KB Output is correct
7 Correct 360 ms 22428 KB Output is correct
8 Correct 368 ms 22840 KB Output is correct
9 Correct 379 ms 22492 KB Output is correct
10 Correct 380 ms 22716 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 20876 KB Output is correct
2 Correct 442 ms 21248 KB Output is correct
3 Correct 407 ms 20832 KB Output is correct
4 Correct 384 ms 21028 KB Output is correct
5 Execution timed out 1028 ms 22340 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 23048 KB Output is correct
2 Correct 433 ms 22752 KB Output is correct
3 Correct 409 ms 22972 KB Output is correct
4 Correct 440 ms 22760 KB Output is correct
5 Correct 444 ms 22972 KB Output is correct
6 Correct 437 ms 23108 KB Output is correct
7 Correct 419 ms 23192 KB Output is correct
8 Correct 424 ms 22972 KB Output is correct
9 Correct 440 ms 23260 KB Output is correct
10 Correct 440 ms 23200 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 3 ms 460 KB Output is correct
22 Correct 4 ms 460 KB Output is correct
23 Correct 3 ms 420 KB Output is correct
24 Correct 9 ms 460 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 3 ms 460 KB Output is correct
27 Correct 3 ms 460 KB Output is correct
28 Correct 5 ms 460 KB Output is correct
29 Correct 3 ms 452 KB Output is correct
30 Correct 3 ms 332 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 22340 KB Output is correct
2 Correct 383 ms 22848 KB Output is correct
3 Correct 410 ms 23096 KB Output is correct
4 Correct 414 ms 22940 KB Output is correct
5 Correct 367 ms 22824 KB Output is correct
6 Correct 388 ms 22440 KB Output is correct
7 Correct 360 ms 22428 KB Output is correct
8 Correct 368 ms 22840 KB Output is correct
9 Correct 379 ms 22492 KB Output is correct
10 Correct 380 ms 22716 KB Output is correct
11 Correct 388 ms 20876 KB Output is correct
12 Correct 442 ms 21248 KB Output is correct
13 Correct 407 ms 20832 KB Output is correct
14 Correct 384 ms 21028 KB Output is correct
15 Execution timed out 1028 ms 22340 KB Time limit exceeded
16 Halted 0 ms 0 KB -