Submission #739738

#	Time	Username	Problem	Language	Result	Execution time	Memory
739738		Toxtaq	Feast (NOI19_feast)	C++17	41 / 100	111 ms	262144 KiB

feast

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<iomanip>
#include<random>
using namespace std;
int n;
vector<int>v;
vector<vector<vector<long long>>>table;
long long rec(int indx, int k, bool last){
	long long res=-1e15;
	if(k < 0)return -1e15;
	if(indx == n && k >= 0)return 0;
	if(indx == n)return -1e15;
	if(table[last][k][indx] != -1e18)return table[last][k][indx];
	if(last){
		res = max(rec(indx + 1, k, 1) + v[indx], rec(indx + 1, k,  0));
	}
	else{
		res = max(rec(indx+ 1, k - 1, 1) + v[indx], rec(indx + 1, k, 0));
	}
	return table[last][k][indx] = res;
}
int main()
{
	int k;
	cin >> n >> k;	
	v.resize(n);
	table.assign(2, vector<vector<long long>>(n, vector<long long>(n, -1e18)));
	for(int i = 0;i < n;++i){
		cin >> v[i];
	}
	cout << max(0LL, rec(0, k, 0));
}

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