Submission #1275943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275943		kbity	Feast (NOI19_feast)	C++20	59 / 100	1096 ms	23092 KiB

feast

// https://oj.uz/problem/view/NOI19_feast
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using LL=long long;
using LD=long double;
#define FOR(i,l,r) for(auto i=(l);i<=(r);++i)
#define ROF(i,l,r) for(auto i=(l);i>=(r);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ITF(e,c) for(auto&e:(c))
#define ssize(x) int(x.size())
#ifdef DEBUG
auto operator<<(auto&o,auto p)->decltype(p.first,o){return o<<'('<<p.first<<", "<<p.second<<')';}
auto operator<<(auto&o,auto&x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

int N,K;
vector<int> A;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  /// input
  {
    cin >> N >> K;
    A.resize(N);
    ITF(e,A) cin >> e;
  }

  /// brute
  vector<vector<vector<LL>>> dp(2,vector<vector<LL>>(K+1,vector<LL>(2,0)));
  {
    dp[0][1][1] = A[0];
    FOR(i,1,N-1) {
      FOR(k,1,K) {
        dp[1][k][0] = max(dp[0][k][0], dp[0][k][1]);
        dp[1][k][1] = max(dp[0][k-1][0], dp[0][k][1]) + A[i];
      }
      swap(dp[0],dp[1]);
    }
  }

  /// output
  {
    cout << max(dp[0][K][0],dp[0][K][1]) << endl;
  }
 
  return 0;
}

• 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