제출 #403872

#제출 시각아이디문제언어결과실행 시간메모리
403872opukittpceno_hhr수열 (APIO14_sequence)C++17
33 / 100
66 ms64500 KiB
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <string> #include <cmath> #include <cstdio> #include <iomanip> #include <fstream> #include <cassert> #include <cstring> #include <unordered_set> #include <unordered_map> #include <numeric> #include <ctime> #include <bitset> #include <complex> #include <chrono> #include <random> #include <functional> using namespace std; #define int long long const int INF = 1e18 + 239; const int N = 1e4 + 7; const int K = 201; int dp[K][N]; int wr[K][N]; int a[N]; int ps[N]; int sc(int i, int j) { return (ps[j] - ps[i]) * (ps[j] - ps[i]); } vector<int> out; void rec(int k, int n) { if (k == 0) return; rec(k - 1, wr[k][n]); out.push_back(n - wr[k][n]); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; k++; int s = 0; for (int i = 0; i < n; i++) { cin >> a[i]; s += a[i] * a[i]; ps[i + 1] = ps[i] + a[i]; } fill(dp[0], dp[0] + N, INF); dp[0][0] = 0; for (int i = 1; i <= k; i++) { for (int j = 0; j <= n; j++) { int p = 0; if (j > 0) { p = wr[i][j - 1]; } while (p + 1 < j && dp[i - 1][p] + sc(p, j) >= dp[i - 1][p + 1] + sc(p + 1, j)) { p++; } dp[i][j] = dp[i - 1][p] + sc(p, j); wr[i][j] = p; } } cout << (ps[n] * ps[n] - dp[k][n]) / 2 << endl; rec(k, n); { int c = 0; for (int i = 0; i + 1 < k; i++) { c += out[i]; cout << c << ' '; } cout << endl; } }
#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...