Submission #1093775

#TimeUsernameProblemLanguageResultExecution timeMemory
1093775muhammadFeast (NOI19_feast)C++17
18 / 100
194 ms262144 KiB
#include <iostream> #include <vector> #include <algorithm> #include <limits.h> using namespace std; int main() { int N, K; cin >> N >> K; vector<int> A(N + 1); for (int i = 1; i <= N; ++i) { cin >> A[i]; } // Initialize the DP arrays vector<vector<long long>> f(N + 1, vector<long long>(K + 1, LLONG_MIN)); vector<vector<long long>> g(N + 1, vector<long long>(K + 1, LLONG_MIN)); // Base case f[0][0] = 0; g[0][0] = 0; // Fill DP tables for (int n = 1; n <= N; ++n) { for (int k = 0; k <= K; ++k) { // Calculate g(n, k) if (k > 0) { g[n][k] = max(g[n - 1][k], f[n - 1][k - 1]) + A[n]; } // Calculate f(n, k) f[n][k] = max(f[n - 1][k], g[n][k]); } } // The answer is f(N, K), i.e., the maximum sum of K subarrays in the first N integers cout << f[N][K] << 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...