답안 #440783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440783	2021-07-03T02:04:59 Z	dongliu0426	Feast (NOI19_feast)	C++14	63 / 100	1000 ms	23260 KB

feast

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #440783

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 0 / 8.0

Subtask #3 18.0 / 18.0

Subtask #4 10.0 / 10.0

Subtask #5 11.0 / 11.0

Subtask #6 20.0 / 20.0

Subtask #7 0 / 29.0

Subtask #1
4.0 / 4.0

Subtask #2
0 / 8.0

Subtask #3
18.0 / 18.0

Subtask #4
10.0 / 10.0

Subtask #5
11.0 / 11.0

Subtask #6
20.0 / 20.0

Subtask #7
0 / 29.0