Submission #107268

#TimeUsernameProblemLanguageResultExecution timeMemory
107268abilSplit the sequence (APIO14_sequence)C++14
49 / 100
678 ms132096 KiB
#include <bits/stdc++.h> #define mk make_pair #define sc second #define fr first #define pb emplace_back #define all(s) s.begin(), s.end() #define sz(s) ( (int)s.size() ) #define int long long using namespace std; const int inf = (int)1e9 + 7 ; const long long mod = 1e9 + 7; const int N = (int)100007; int n, k, par[207][N],dp[3][N],arr[N]; int f(int l,int r){ return arr[l] * (arr[r] - arr[l]); } void solve(int g,int l,int r,int optl,int optr){ if(l > r){ return; } int mid = (l + r) >> 1, opt; for(int i = optl; i <= min(optr,mid); i++){ if(dp[(g % 2)][mid] <= dp[(g - 1) % 2][i] + f(i,mid)){ dp[(g % 2)][mid] = dp[(g - 1) % 2][i] + f(i,mid); opt = i; } } par[g][mid] = opt; solve(g,l,mid - 1, optl, opt); solve(g,mid + 1, r, opt, optr); } main(){ cin >> n >> k; for(int i = 1;i <= n; i++){ cin >> arr[i]; arr[i] = arr[i - 1] + arr[i]; } for(int i = 1;i <= k; i++){ solve(i,1,n,1,n); } cout << dp[k % 2][n] << '\n'; vector<int > ans; while(par[k][n]){ ans.pb(par[k][n]); n = par[k][n]; k--; } for(int i = ans.size() - 1; i >= 0; i--){ cout << ans[i] << " "; } } /* 7 3 4 1 3 4 0 2 3 */

Compilation message (stderr)

sequence.cpp:36:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
sequence.cpp: In function 'void solve(long long int, long long int, long long int, long long int, long long int)':
sequence.cpp:33:12: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
       solve(g,l,mid - 1, optl, opt);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...