Submission #722031

#TimeUsernameProblemLanguageResultExecution timeMemory
722031BobonbushSplit the sequence (APIO14_sequence)C++17
78 / 100
1404 ms81120 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MODULO = 12; template<class X , class Y> bool Maximize(X &x , Y y) { if(x < y) { x = y; return true; } return false; } template<class X ,class Y> bool Minimize(X &x , Y y) { if(x > y) { x = y; return true; } return false; } template<class X ,class Y> void Add(X &x , Y y) { x += y; if(x >= MODULO) x-= MODULO; } template<class X ,class Y> void Sub(X & x , Y y) { x -= y; if(x < 0 ) x += MODULO; } const int N = 1e5+1; long long dp[2][N]; long long a[N]; int P[201][N]; long long cost(int l ,int r) { assert(l <= r); return (a[r] - a[l-1]) * (a[r] - a[l-1]); } void conq(int l ,int r ,int opt_l , int opt_r , bool cur , int k) { if(l > r)return ; int mid = (l+r) >> 1; dp[cur][mid] = (1ll << 61); int opt; for(int i = opt_l ; i <=min(mid -1 , opt_r) ; i++) { long long sta = dp[!cur][i] + cost(i +1 , mid); if(Minimize(dp[cur][mid] , sta)) { opt = i; } } P[k][mid] = opt; conq(l , mid-1 , opt_l , opt , cur , k); conq(mid+1 , r , opt , opt_r , cur , k ); } vector<int>List; void trace(int k , int i) { if(k == 0) { return ; } trace(k-1 , P[k][i] ); cout << P[k][i] << ' '; } int n ; int k; void Input() { cin >> n >> k; for(int i = 1; i <= n ; i++) { cin >> a[i]; a[i] += a[i-1]; } } void Process() { bool cur = false; for(int i = 1 ; i <= n ; i++) { dp[cur][i] = cost(1 , i); } for(int g = 1 ; g <= k ; g++) { cur ^= 1; conq(g , n , g , n , cur , g ); } cout << (cost(1 , n ) - dp[cur][n]) /2LL <<'\n'; trace(k , n); } int main() { ios_base :: sync_with_stdio(0);cin.tie(0); int test = 1; while(test--) { Input(); Process(); cout <<'\n'; } return 0; }

Compilation message (stderr)

sequence.cpp: In function 'void conq(int, int, int, int, bool, int)':
sequence.cpp:64:9: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     conq(mid+1 , r , opt , opt_r , cur , k );
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...