Submission #938588

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
938588	2024-03-05T10:44:01 Z	Lilypad	Feast (NOI19_feast)	C++14	41 / 100	64 ms	127924 KB

feast

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define pb push_back
#define fi first
#define se second

const ll N = 2003;

ll n,k,sum,b[N];
ll mins,pos,idx;
vector<ll> a;
ll memo[N][N][2];

ll dp(ll x, ll y, ll stat) {
	if(x == idx+1) return 0;
	ll tmp = memo[x][y][stat];
	if(tmp != -1) return tmp;
	if(stat == 0) {
		tmp = dp(x+1,y,0);
		if(y > 0) {
			tmp = max(tmp,dp(x+1,y-1,1)+a[x]);
		}
	}
	else {
		tmp = max(dp(x+1,y,0),dp(x+1,y,1)+a[x]);
	}
	return memo[x][y][stat] = tmp;
}

int main() {
	memset(memo,-1,sizeof(memo));
	cin >> n >> k;
	for(int i=1; i<=n; i++) {
		cin >> b[i];
	}
	a.pb(0);
	for(int i=1; i<=n; i++) {
		if(b[i] >= 0) {
			sum += b[i];
			if(mins < 0) {
				a.pb(mins);
				mins = 0;
			}
		}
		else {
			mins += b[i];
			if(sum > 0) {
				a.pb(sum);
				sum = 0;
				pos++;
			}
		}
	}
	if(sum > 0) {
		a.pb(sum);
		pos++;
	}
	if(mins < 0) a.pb(mins);
	idx = a.size()-1;
	cout << dp(1,k,0) << endl;
}

Subtask #1

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	61 ms	127924 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	8 ms	63320 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	64 ms	127728 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	63064 KB	Output is correct
2	Correct	8 ms	63064 KB	Output is correct
3	Correct	8 ms	63192 KB	Output is correct
4	Correct	8 ms	63200 KB	Output is correct
5	Correct	8 ms	63124 KB	Output is correct
6	Correct	8 ms	63068 KB	Output is correct
7	Correct	10 ms	63068 KB	Output is correct
8	Correct	9 ms	63120 KB	Output is correct
9	Correct	10 ms	63064 KB	Output is correct
10	Correct	8 ms	63068 KB	Output is correct

Subtask #5

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	63064 KB	Output is correct
2	Correct	8 ms	63064 KB	Output is correct
3	Correct	8 ms	63192 KB	Output is correct
4	Correct	8 ms	63200 KB	Output is correct
5	Correct	8 ms	63124 KB	Output is correct
6	Correct	8 ms	63068 KB	Output is correct
7	Correct	10 ms	63068 KB	Output is correct
8	Correct	9 ms	63120 KB	Output is correct
9	Correct	10 ms	63064 KB	Output is correct
10	Correct	8 ms	63068 KB	Output is correct
11	Correct	9 ms	63068 KB	Output is correct
12	Correct	9 ms	63148 KB	Output is correct
13	Correct	8 ms	63068 KB	Output is correct
14	Correct	9 ms	63064 KB	Output is correct
15	Correct	8 ms	63068 KB	Output is correct
16	Correct	8 ms	63064 KB	Output is correct
17	Correct	9 ms	63068 KB	Output is correct
18	Correct	9 ms	63064 KB	Output is correct
19	Correct	9 ms	63168 KB	Output is correct
20	Correct	9 ms	63068 KB	Output is correct

Subtask #6

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	63064 KB	Output is correct
2	Correct	8 ms	63064 KB	Output is correct
3	Correct	8 ms	63192 KB	Output is correct
4	Correct	8 ms	63200 KB	Output is correct
5	Correct	8 ms	63124 KB	Output is correct
6	Correct	8 ms	63068 KB	Output is correct
7	Correct	10 ms	63068 KB	Output is correct
8	Correct	9 ms	63120 KB	Output is correct
9	Correct	10 ms	63064 KB	Output is correct
10	Correct	8 ms	63068 KB	Output is correct
11	Correct	9 ms	63068 KB	Output is correct
12	Correct	9 ms	63148 KB	Output is correct
13	Correct	8 ms	63068 KB	Output is correct
14	Correct	9 ms	63064 KB	Output is correct
15	Correct	8 ms	63068 KB	Output is correct
16	Correct	8 ms	63064 KB	Output is correct
17	Correct	9 ms	63068 KB	Output is correct
18	Correct	9 ms	63064 KB	Output is correct
19	Correct	9 ms	63168 KB	Output is correct
20	Correct	9 ms	63068 KB	Output is correct
21	Correct	15 ms	63324 KB	Output is correct
22	Correct	16 ms	63324 KB	Output is correct
23	Correct	16 ms	63324 KB	Output is correct
24	Correct	13 ms	63324 KB	Output is correct
25	Correct	15 ms	63320 KB	Output is correct
26	Correct	13 ms	63284 KB	Output is correct
27	Correct	15 ms	63360 KB	Output is correct
28	Correct	10 ms	63320 KB	Output is correct
29	Correct	12 ms	63324 KB	Output is correct
30	Correct	10 ms	63324 KB	Output is correct

Subtask #7

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	61 ms	127924 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-