Submission #1275942

#TimeUsernameProblemLanguageResultExecution timeMemory
1275942kbityFeast (NOI19_feast)C++20
0 / 100
249 ms327680 KiB
// 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(N,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[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]); dp[i][k][1] = max(dp[i-1][k-1][0], dp[i-1][k][1]) + A[i]; } } } /// output { cout << max(dp[N-1][K][0],dp[N-1][K][1]) << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...