Submission #503846

#TimeUsernameProblemLanguageResultExecution timeMemory
503846sumit_kk10Split the sequence (APIO14_sequence)C++17
50 / 100
2086 ms31932 KiB
#include <bits/stdc++.h> #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) #define S second #define F first #define pb push_back using namespace std; const int N = 2e5 + 5; const int MOD = 1e9 + 7; long long n, k, a[N], suf[N]; void solve(){ cin >> n >> k; pair<long long, int> dp[n + 1][k + 1]; for(int i = 1; i <= n; ++i){ cin >> a[i]; for(int j = 1; j <= k; ++j) dp[i][j].F = INT_MIN; dp[i][0].F = 0; } for(int i = n; i >= 1; --i) suf[i] = suf[i + 1] + a[i]; for(int i = n; i >= 1; --i){ for(int bars = 1; bars <= k; ++bars){ if(n - i < bars) break; long long sum = a[i]; for(int j = i + 1; j <= n; ++j){ if(dp[j][bars - 1].F + (sum * suf[j]) > dp[i][bars].F){ dp[i][bars].F = dp[j][bars - 1].F + (sum * suf[j]); dp[i][bars].S = j; } sum += a[j]; } if(dp[i + 1][bars].F > dp[i][bars].F){ dp[i][bars].F = dp[i + 1][bars].F; dp[i][bars].S = dp[i + 1][bars].S; } } } cout << dp[1][k].F << '\n'; int pos = 1, ct = k; while(ct > 0){ cout << dp[pos][ct].S - 1 << ' '; pos = dp[pos][ct].S; --ct; } } int main(){ fast; int t = 1; // cin >> t; while(t--) solve(); 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...