제출 #624011

#제출 시각아이디문제언어결과실행 시간메모리
624011Arnch수열 (APIO14_sequence)C++17
50 / 100
213 ms5280 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 = 1e3 + 10, MAXK = 2e2 + 10; ll a[N], ps[N], dp[N][MAXK]; pair<ll, ll> par[N][MAXK]; bool mark[N]; 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...