Submission #1139738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139738		NAMIN	Feast (NOI19_feast)	C++20	21 / 100	1095 ms	327680 KiB

feast

/*
ID: NAMIN
TASK:
LANG: C++
*/
#include <iostream>
#include <numeric>
#include <math.h>
#include <set>
#include <unordered_set>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>
#include <fstream>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <deque>
#include <assert.h>
#include <cstring>

#define gcd __gcd
#define endl "\n"
#define ll long long
#define ld long double

using namespace std;

const int MOD = 1e9+7;

void solve(){
	int n,k;
	cin >> n >> k;
	vector<int> a(n);
	for(int i=0;i<n;i++)
		cin >> a[i];

	ll dp[n][k+1];
	memset(dp,-1e9,sizeof(dp));
	for(int i=0;i<n;i++)
		dp[i][0] = 0;

	for(int i=1;i<=k;i++){
		for(int j=i-1;j<n;j++){
			ll cost = 0;
			ll mxCost = 0;
			for(int p=j;p>=i-1;p--){
				cost += a[p];
				mxCost = max(mxCost,cost);
				if(p > 0 && i > 0)
					dp[j][i] = max(dp[j][i],dp[p-1][i-1]+mxCost);
				else
					dp[j][i] = max(dp[j][i],mxCost);
			}
		}
	}

	ll ans = 0;
	for(int i=0;i<n;i++){
		ans = max(ans,dp[i][k]);
	}
	cout << ans << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	//cin >> t;
 	while(t--){
		solve();
	}
	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