Submission #619628

#	Time	Username	Problem	Language	Result	Execution time	Memory
619628		Valenz	Feast (NOI19_feast)	C++14	21 / 100	1086 ms	262144 KiB

feast

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
signed main()
{
	int n,k;
	cin >> n >> k;
	vector<int> a(n+1);
	a[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];	
		a[i]+=a[i-1];
	}
	vector<vector<int>> dp(n+1,vector<int>(k+1,0));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			dp[i][j]=max(dp[i][j],dp[i-1][j]);
			if(j>0)
			{
				for(int l=0;l<i;l++)
				{
					dp[i][j]=max(dp[i][j],dp[l][j-1]+(a[i]-a[l]));
				}
			}
		}
	}
	cout << dp[n][k] << '\n';
 
	return 0;
}

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