oj.uz

Submission #938593

# Submission time Handle Problem Language Result Execution time Memory
938593 2024-03-05T10:53:04 Z Lilypad Feast (NOI19_feast) C++14
63 / 100
 123 ms 70996 KB 
#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[300005],pref[300005];
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];
	}
	if(k == 1) {
		mins = 1e18;
		ll ans = 0;
		for(int i=1; i<=n; i++) {
			pref[i] = pref[i-1] + b[i];
			ans = max(ans,pref[i]-mins);
			mins = min(mins,pref[i]);
		}
		cout << ans << endl;
		return 0;
	}
	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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 67932 KB Output is correct
2 Correct 88 ms 67668 KB Output is correct
3 Correct 88 ms 67692 KB Output is correct
4 Correct 108 ms 67664 KB Output is correct
5 Correct 96 ms 67868 KB Output is correct
6 Correct 89 ms 67728 KB Output is correct
7 Correct 85 ms 67664 KB Output is correct
8 Correct 88 ms 67808 KB Output is correct
9 Correct 87 ms 67668 KB Output is correct
10 Correct 87 ms 67920 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 67696 KB Output is correct
2 Incorrect 52 ms 67668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 67668 KB Output is correct
2 Correct 92 ms 70692 KB Output is correct
3 Correct 98 ms 70720 KB Output is correct
4 Correct 96 ms 70800 KB Output is correct
5 Correct 97 ms 70736 KB Output is correct
6 Correct 95 ms 70896 KB Output is correct
7 Correct 99 ms 70996 KB Output is correct
8 Correct 93 ms 70736 KB Output is correct
9 Correct 123 ms 70848 KB Output is correct
10 Correct 94 ms 70736 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 66136 KB Output is correct
2 Correct 8 ms 66140 KB Output is correct
3 Correct 10 ms 66140 KB Output is correct
4 Correct 8 ms 66140 KB Output is correct
5 Correct 8 ms 66140 KB Output is correct
6 Correct 8 ms 66140 KB Output is correct
7 Correct 8 ms 66208 KB Output is correct
8 Correct 8 ms 66140 KB Output is correct
9 Correct 9 ms 66140 KB Output is correct
10 Correct 9 ms 66268 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 66136 KB Output is correct
2 Correct 8 ms 66140 KB Output is correct
3 Correct 10 ms 66140 KB Output is correct
4 Correct 8 ms 66140 KB Output is correct
5 Correct 8 ms 66140 KB Output is correct
6 Correct 8 ms 66140 KB Output is correct
7 Correct 8 ms 66208 KB Output is correct
8 Correct 8 ms 66140 KB Output is correct
9 Correct 9 ms 66140 KB Output is correct
10 Correct 9 ms 66268 KB Output is correct
11 Correct 8 ms 66140 KB Output is correct
12 Correct 8 ms 66136 KB Output is correct
13 Correct 9 ms 66140 KB Output is correct
14 Correct 8 ms 66232 KB Output is correct
15 Correct 9 ms 66176 KB Output is correct
16 Correct 9 ms 66140 KB Output is correct
17 Correct 8 ms 66140 KB Output is correct
18 Correct 8 ms 66140 KB Output is correct
19 Correct 9 ms 66140 KB Output is correct
20 Correct 8 ms 66140 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 66136 KB Output is correct
2 Correct 8 ms 66140 KB Output is correct
3 Correct 10 ms 66140 KB Output is correct
4 Correct 8 ms 66140 KB Output is correct
5 Correct 8 ms 66140 KB Output is correct
6 Correct 8 ms 66140 KB Output is correct
7 Correct 8 ms 66208 KB Output is correct
8 Correct 8 ms 66140 KB Output is correct
9 Correct 9 ms 66140 KB Output is correct
10 Correct 9 ms 66268 KB Output is correct
11 Correct 8 ms 66140 KB Output is correct
12 Correct 8 ms 66136 KB Output is correct
13 Correct 9 ms 66140 KB Output is correct
14 Correct 8 ms 66232 KB Output is correct
15 Correct 9 ms 66176 KB Output is correct
16 Correct 9 ms 66140 KB Output is correct
17 Correct 8 ms 66140 KB Output is correct
18 Correct 8 ms 66140 KB Output is correct
19 Correct 9 ms 66140 KB Output is correct
20 Correct 8 ms 66140 KB Output is correct
21 Correct 13 ms 66136 KB Output is correct
22 Correct 16 ms 66392 KB Output is correct
23 Correct 15 ms 66140 KB Output is correct
24 Correct 13 ms 66140 KB Output is correct
25 Correct 15 ms 66364 KB Output is correct
26 Correct 14 ms 66176 KB Output is correct
27 Correct 17 ms 66396 KB Output is correct
28 Correct 10 ms 66140 KB Output is correct
29 Correct 10 ms 66240 KB Output is correct
30 Correct 9 ms 66220 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 67932 KB Output is correct
2 Correct 88 ms 67668 KB Output is correct
3 Correct 88 ms 67692 KB Output is correct
4 Correct 108 ms 67664 KB Output is correct
5 Correct 96 ms 67868 KB Output is correct
6 Correct 89 ms 67728 KB Output is correct
7 Correct 85 ms 67664 KB Output is correct
8 Correct 88 ms 67808 KB Output is correct
9 Correct 87 ms 67668 KB Output is correct
10 Correct 87 ms 67920 KB Output is correct
11 Correct 50 ms 67696 KB Output is correct
12 Incorrect 52 ms 67668 KB Output isn't correct
13 Halted 0 ms 0 KB -