oj.uz

Submission #440784

# Submission time Handle Problem Language Result Execution time Memory
440784 2021-07-03T02:07:54 Z dongliu0426 Feast (NOI19_feast) C++14
63 / 100
 1000 ms 20208 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 390 ms 19616 KB Output is correct
2 Correct 407 ms 19992 KB Output is correct
3 Correct 406 ms 20208 KB Output is correct
4 Correct 413 ms 20040 KB Output is correct
5 Correct 372 ms 19968 KB Output is correct
6 Correct 365 ms 19632 KB Output is correct
7 Correct 378 ms 19632 KB Output is correct
8 Correct 380 ms 20028 KB Output is correct
9 Correct 379 ms 19676 KB Output is correct
10 Correct 380 ms 19800 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 19760 KB Output is correct
2 Correct 409 ms 20196 KB Output is correct
3 Correct 368 ms 19672 KB Output is correct
4 Correct 349 ms 19904 KB Output is correct
5 Execution timed out 1085 ms 19588 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 20012 KB Output is correct
2 Correct 401 ms 19760 KB Output is correct
3 Correct 442 ms 19980 KB Output is correct
4 Correct 447 ms 19716 KB Output is correct
5 Correct 423 ms 19952 KB Output is correct
6 Correct 435 ms 19964 KB Output is correct
7 Correct 474 ms 20140 KB Output is correct
8 Correct 411 ms 19960 KB Output is correct
9 Correct 447 ms 20196 KB Output is correct
10 Correct 505 ms 20152 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 204 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 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 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 204 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 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 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 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 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 204 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 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 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 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 4 ms 332 KB Output is correct
22 Correct 4 ms 436 KB Output is correct
23 Correct 4 ms 332 KB Output is correct
24 Correct 5 ms 332 KB Output is correct
25 Correct 3 ms 332 KB Output is correct
26 Correct 3 ms 344 KB Output is correct
27 Correct 4 ms 332 KB Output is correct
28 Correct 3 ms 332 KB Output is correct
29 Correct 4 ms 332 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 390 ms 19616 KB Output is correct
2 Correct 407 ms 19992 KB Output is correct
3 Correct 406 ms 20208 KB Output is correct
4 Correct 413 ms 20040 KB Output is correct
5 Correct 372 ms 19968 KB Output is correct
6 Correct 365 ms 19632 KB Output is correct
7 Correct 378 ms 19632 KB Output is correct
8 Correct 380 ms 20028 KB Output is correct
9 Correct 379 ms 19676 KB Output is correct
10 Correct 380 ms 19800 KB Output is correct
11 Correct 423 ms 19760 KB Output is correct
12 Correct 409 ms 20196 KB Output is correct
13 Correct 368 ms 19672 KB Output is correct
14 Correct 349 ms 19904 KB Output is correct
15 Execution timed out 1085 ms 19588 KB Time limit exceeded
16 Halted 0 ms 0 KB -