Submission #333054

#	Time	Username	Problem	Language	Result	Execution time	Memory
333054		guka415	Feast (NOI19_feast)	C++14	41 / 100	40 ms	66944 KiB

feast

#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <list>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int sz = 3e3;
int n, k;
ll a[sz], dpy[sz][sz], dpn[sz][sz];

int main() {
	fast;
	cin >> n >> k;
	foru(i, 0, n)cin >> a[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			dpy[i][j] = a[i - 1] + max(dpn[i - 1][j - 1], dpy[i - 1][j]);
			dpn[i][j] = max(dpn[i - 1][j], dpy[i - 1][j]);
		}
	}
	cout << max(dpy[n][k], dpn[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: 20 / 20
• Subtask 7: 0 / 29