Submission #1025601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025601		ach00	Feast (NOI19_feast)	C++14	41 / 100	177 ms	192548 KiB

feast

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
vector<ll> W;
vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(2005, vector<ll>(2005, -1)));

ll solve(int i, int l, bool w) {
    if(dp[w][i][l] != -1) return dp[w][i][l];
    if(l > k || i >= n) return 0;
    ll ans = numeric_limits<int>::min();
    if(w == false) {
        ans = max(ans, solve(i+1, l , false));
        ans = max(ans, solve(i+1, l+1, true));
    } else {
        ans = max(ans, solve(i+1, l, true));
        ans = max(ans, solve(i+1, l, false));
    }
    ans += (w) ? W[i] : 0;
    dp[w][i][l] = ans;
    return ans;
}

int main() {
    cin >> n >> k;
    W.resize(n); for(auto &a : W) cin >> a;
    cout << max(solve(0, 0, false), solve(0, 1, true));
}

• 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