Submission #623996

#TimeUsernameProblemLanguageResultExecution timeMemory
623996ArnchSplit the sequence (APIO14_sequence)C++17
Compilation error
0 ms0 KiB
// oooo /* har chi delet mikhad bebar ~ gitar o ba khodet nabar! ~ ;Amoo_Hasan; */ #include<bits/stdc++.h> //#pragma GCC optimize("O3,no-stack-protector,unroll-loops") //#pragma GCC target("avx2,fma") using namespace std; typedef long long ll; typedef long double ld; #define Sz(x) int((x).size()) #define All(x) (x).begin(), (x).end() #define wtf(x) cout<<#x <<" : " <<x <<endl #define mak make_pair constexpr ll INF = 1e18, N = 1e5 + 10, MAXK = 2e2 + 10; ll a[N], ps[N], dp[N][MAXK]; pair<ll, ll> par[N][MAXK]; bool mark[N]; /*inline pair<ll, ll> Solve(int l, int r) { ll ans = 0, sum = 0, pos = 0; sum = ps[r - 1] - ps[l - 1]; for(int i = l; i < r - 1; i++) { ll val = ps[i] - ps[l - 1]; val *= (sum - val); if(val >= ans) { ans = val, pos = i; } } return mak(ans, pos + 1); } vector<int> vc; vc.push_back(1), vc.push_back(n + 1); ll sum = 0; while(k--) { ll mx = 0, ind = 0; for(int i = 0; i < Sz(vc) - 1; i++) { int l = vc[i], r = vc[i + 1]; if(r - l == 1) continue; pair<ll, ll> p = Solve(l, r); if(p.first >= mx) ind = p.second; mx = max(mx, p.first); } sum += mx; vc.push_back(ind); sort(All(vc)); } cout<<sum <<endl; for(auto i : vc) { if(i != 1 && i != n + 1) cout<<i - 1 <<" "; }*/ int main() { ios :: sync_with_stdio(0), cin.tie(0); int n, k; cin >>n >>k; for(int i = 1; i <= n; i++) cin >>a[i]; for(int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i]; memset(dp, 63, sizeof(dp)); dp[0][0] = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= min(k + 1, i); j++) { ll val = INF; for(int x = i - 1; x >= 0; x--) { if(dp[x][j - 1] >= INF) continue; ll cnt = dp[x][j - 1] + (ps[i] - ps[x]) * (ps[i] - ps[x]); if(cnt < val) { val = cnt; par[i][j] = mak(x, j - 1); } } dp[i][j] = val; } } /* ll ans = ps[n] * ps[n]; ans -= dp[n][k + 1]; ans /= 2; cout<<ans <<endl; */ /* vector<int> pos;

Compilation message (stderr)

sequence.cpp:96:1: error: unterminated comment
   96 | /*
      | ^
sequence.cpp: In function 'int main()':
sequence.cpp:88:2: error: expected '}' at end of input
   88 |  }
      |  ^
sequence.cpp:64:12: note: to match this '{'
   64 | int main() {
      |            ^