Submission #739880

#	Time	Username	Problem	Language	Result	Execution time	Memory
739880		MODDI	Feast (NOI19_feast)	C++14	63 / 100	118 ms	63700 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, k;
vl 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;
	arr.resize(n);
	int cnt = 0;
	for(int i = 0; i < n; i++){
		cin>>arr[i];
		if(arr[i] < 0)	cnt++;
	}
	if(cnt == 0){
		ll ans = 0;
		for(int i = 0; i < n; i++)	ans += arr[i];
		
		cout<<ans<<endl;
	}
	else if(cnt == 1){
		ll left = 0, right = 0, flag = 0, pos = -1;
		for(int i = 0; i < n; i++){
			if(arr[i] < 0){
				pos = i;
				flag = 1;
				continue;
			}
			else if(flag == 0)	left += arr[i];
			else right += arr[i];
		}
		cout<<max(max(left, right), left + right + arr[pos]);
	}
	else if(k == 1){
		ll ans = 0, help = 0;
		for(int i = 0; i < n; i++){
			help += arr[i];
			if(ans < help)	ans = help;
			if(help < 0)	help = 0;
		}
		cout<<ans<<endl;
	}
	else{
		memset(dp, -1, sizeof dp);
		cout<<f(0, 0, 0)<<endl;
	}
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 0 / 29