답안 #572189

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572189	2022-06-03T23:43:00 Z	MODDI	Feast (NOI19_feast)	C++14	41 / 100	114 ms	63800 KB

feast

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, k;
vi arr;
ll dp[2010][2010][2];
ll f(int at, int segments, int taken){
	if(at >= n)
		return 0;
	if(segments > k)
		return 0;
	if(dp[at][segments][taken] != -1)
		return dp[at][segments][taken];
		
	ll best = 0;
	best = max(best, arr[at] + f(at + 1, segments, 1));
	if(taken == 0)
		best = max(best, f(at + 1, segments, 0));
	if(segments + 1 < k && taken == 1)
		best = max(best, f(at + 1, segments + 1, 0));
	return dp[at][segments][taken] = best;
}
int main(){
	cin>>n>>k;
	for(int i = 0; i < n; i++){
		int a;
		cin>>a;
		arr.pb(a);
	}
	if(n > 2500 || k > 2500)
	{
		cout<<-1<<endl;
		return 0;
	}
	memset(dp, -1, sizeof(dp));
	cout<<f(0, 0,0)<<endl;
}

Subtask #1

0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	101 ms	2400 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	64 ms	2440 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	114 ms	2524 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	63444 KB	Output is correct
2	Correct	25 ms	63444 KB	Output is correct
3	Correct	26 ms	63456 KB	Output is correct
4	Correct	27 ms	63516 KB	Output is correct
5	Correct	25 ms	63436 KB	Output is correct
6	Correct	25 ms	63540 KB	Output is correct
7	Correct	24 ms	63444 KB	Output is correct
8	Correct	24 ms	63444 KB	Output is correct
9	Correct	25 ms	63504 KB	Output is correct
10	Correct	25 ms	63436 KB	Output is correct

Subtask #5

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	63444 KB	Output is correct
2	Correct	25 ms	63444 KB	Output is correct
3	Correct	26 ms	63456 KB	Output is correct
4	Correct	27 ms	63516 KB	Output is correct
5	Correct	25 ms	63436 KB	Output is correct
6	Correct	25 ms	63540 KB	Output is correct
7	Correct	24 ms	63444 KB	Output is correct
8	Correct	24 ms	63444 KB	Output is correct
9	Correct	25 ms	63504 KB	Output is correct
10	Correct	25 ms	63436 KB	Output is correct
11	Correct	25 ms	63436 KB	Output is correct
12	Correct	27 ms	63540 KB	Output is correct
13	Correct	27 ms	63428 KB	Output is correct
14	Correct	25 ms	63528 KB	Output is correct
15	Correct	24 ms	63436 KB	Output is correct
16	Correct	25 ms	63436 KB	Output is correct
17	Correct	30 ms	63596 KB	Output is correct
18	Correct	25 ms	63468 KB	Output is correct
19	Correct	29 ms	63540 KB	Output is correct
20	Correct	28 ms	63468 KB	Output is correct

Subtask #6

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	63444 KB	Output is correct
2	Correct	25 ms	63444 KB	Output is correct
3	Correct	26 ms	63456 KB	Output is correct
4	Correct	27 ms	63516 KB	Output is correct
5	Correct	25 ms	63436 KB	Output is correct
6	Correct	25 ms	63540 KB	Output is correct
7	Correct	24 ms	63444 KB	Output is correct
8	Correct	24 ms	63444 KB	Output is correct
9	Correct	25 ms	63504 KB	Output is correct
10	Correct	25 ms	63436 KB	Output is correct
11	Correct	25 ms	63436 KB	Output is correct
12	Correct	27 ms	63540 KB	Output is correct
13	Correct	27 ms	63428 KB	Output is correct
14	Correct	25 ms	63528 KB	Output is correct
15	Correct	24 ms	63436 KB	Output is correct
16	Correct	25 ms	63436 KB	Output is correct
17	Correct	30 ms	63596 KB	Output is correct
18	Correct	25 ms	63468 KB	Output is correct
19	Correct	29 ms	63540 KB	Output is correct
20	Correct	28 ms	63468 KB	Output is correct
21	Correct	40 ms	63692 KB	Output is correct
22	Correct	60 ms	63712 KB	Output is correct
23	Correct	48 ms	63624 KB	Output is correct
24	Correct	45 ms	63628 KB	Output is correct
25	Correct	52 ms	63716 KB	Output is correct
26	Correct	36 ms	63700 KB	Output is correct
27	Correct	41 ms	63704 KB	Output is correct
28	Correct	27 ms	63628 KB	Output is correct
29	Correct	27 ms	63800 KB	Output is correct
30	Correct	26 ms	63684 KB	Output is correct

Subtask #7

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	101 ms	2400 KB	Output isn't correct
2	Halted	0 ms	0 KB	-