답안 #440784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440784	2021-07-03T02:07:54 Z	dongliu0426	Feast (NOI19_feast)	C++14	63 / 100	1000 ms	20208 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	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

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

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

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

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

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

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

답안 #440784

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