제출 #212747

#제출 시각아이디문제언어결과실행 시간메모리
212747kig9981수열 (APIO14_sequence)C++17
100 / 100
1528 ms81112 KiB
#include <bits/stdc++.h> #ifdef NON_SUBMIT #define TEST(n) (n) #else #define TEST(n) ((void)0) #endif using namespace std; int PS[100001], P[201][100001]; long long D[2][100001]; void solve(int k, int l, int r, int s, int e) { if (l > r || s > e) return; int m = (s + e) >> 1, L = min(m, r); D[k & 1][m] = 0x7fffffffffffffffLL; for (int i = l; i <= L; i++) { if (D[k & 1][m] > D[(k - 1) & 1][i] + 1LL * (PS[m] - PS[i])*(PS[m] - PS[i])) { D[k & 1][m] = D[(k - 1) & 1][i] + 1LL * (PS[m] - PS[i])*(PS[m] - PS[i]); P[k][m] = i; } } solve(k, l, P[k][m], s, m - 1); solve(k, P[k][m], r, m + 1, e); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); TEST(freopen("input.txt", "r", stdin)); TEST(freopen("output.txt", "w", stdout)); int N, K; cin >> N >> K; for (int i = 1; i <= N; i++) { cin >> PS[i]; PS[i] += PS[i - 1]; D[0][i] = 1LL * PS[i] * PS[i]; } for (int i = 1; i <= K; i++) { solve(i, i, N, i, N); } cout << (1LL * PS[N] * PS[N] - D[K & 1][N]) / 2 << '\n'; for (; K; K--) { cout << P[K][N] << ' '; N = P[K][N]; } 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...