제출 #623998

#제출 시각아이디문제언어결과실행 시간메모리
623998Arnch수열 (APIO14_sequence)C++17
0 / 100
66 ms131072 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; pair<ll, ll> p = mak(n, k + 1); while(p.second > 0) { p = par[p.first][p.second]; if(p.first > 0) pos.push_back(p.first); } while(!pos.empty()) { cout<<pos.back() <<" "; pos.pop_back(); }*/ 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...