제출 #443185

#제출 시각아이디문제언어결과실행 시간메모리
443185hivakarami수열 (APIO14_sequence)C++14
71 / 100
158 ms131076 KiB
#include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #define f first #define s second #define pb push_back #define pii pair<int, int> const int N = 1e5 + 2; const int K = 201; const ll inf = 1e16; const ll mod = 924844033; const int lg = 20; ll ps[N], dp[N][K], a[N]; int op[N][K]; inline ll get(int l, int r) { ll sum = ps[r] - ps[l]; return (sum * (sum-1)) / 2; } inline void solve(int l, int r, int opl, int opr, int k) { //cout << l << ' ' << r << ' ' << opl << ' ' << opr << endl; if(l + 1 == r) { int mid = l; op[mid][k] = opl; for(int i = opl; i < min(mid, opr); i++) { if(dp[mid][k] > dp[i][k-1] + get(i+1, mid+1)) { dp[mid][k] = dp[i][k-1] + get(i+1, mid+1); op[mid][k] = i; } } return; } int mid = (l + r) / 2; op[mid][k] = opl; for(int i = opl; i < min(mid, opr); i++) { if(dp[mid][k] > dp[i][k-1] + get(i+1, mid+1)) { dp[mid][k] = dp[i][k-1] + get(i+1, mid+1); op[mid][k] = i; } } solve(l, mid, opl, op[mid][k]+1, k); solve(mid, r, op[mid][k], opr, k); } int main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); int n, k; cin >> n >> k; k++; for(int i = 0; i < n; i++) { cin >> a[i]; for(int j = 0; j <= k; j++) dp[i][j] = inf; } for(int i = 1; i <= n; i++) ps[i] = ps[i-1] + a[i-1]; for(int i = 0; i < n; i++) { dp[i][1] = get(0, i+1); } for(int i = 2; i <= k; i++) solve(0, n, 0, n, i); /* for(int j = 1; j <= k; j++) for(int i = 0; i < n; i++) cout << i << ' ' << j << ' ' << dp[i][j] << endl; */ cout << dp[n-1][1] - dp[n-1][k] << endl; int i = n-1, j = k; while(j > 1) { cout << op[i][j] + 1 << ' '; //v.pb(op[i][j] + 1); i = op[i][j]; j--; } cout << endl; 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...