Submission #833319

#	Time	Username	Problem	Language	Result	Execution time	Memory
833319		veehj	Feast (NOI19_feast)	C++17	59 / 100	261 ms	262144 KiB

feast

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
int n, k;
vector<ll> a = {};

void s(){
    vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(k+1, vector<ll>(2, -1e15)));
    ll ans=0;
    dp[0][0][1]=0; dp[0][0][0]=0;
    for(int i=1; i<=n; i++){
        dp[i][0][0]=0;
        for(int j=1; j<=k; j++){    
            dp[i][j][0]=max(dp[i-1][j][1], dp[i-1][j][0]);
            dp[i][j][1]=max(dp[i-1][j][1], dp[i-1][j-1][0])+a[i-1];
            // cout << i << ' ' << j << ' ' << dp[i][j][0] << ' ' << dp[i][j][1] << endl;
			ans=max({ans,dp[i][j][0],dp[i][j][1]});
        }
    }
    cout << ans << endl;
}

void f() {
  ll ans = 0, nw = 0;
  for (auto& u : a) {
    nw = max(0LL, nw + u);
    ans = max(ans, nw);
  }
  cout << ans << endl;
  return;
}

int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    ll x;
    cin >> x;
    a.pb(x);
  }
  if (k == 1) {
    f();
    return 0;
  }
  s();
}

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