제출 #13640

#제출 시각아이디문제언어결과실행 시간메모리
13640tncks0121수열 (APIO14_sequence)C++14
0 / 100
0 ms84560 KiB
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <string> #include <functional> #include <vector> #include <numeric> #include <deque> #include <utility> #include <bitset> #include <limits.h> #include <iostream> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long llu; typedef double lf; typedef unsigned int uint; typedef long double llf; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N_ = 100500; const int K_ = 205; int N, K; ll S[N_]; ll table[2][N_]; int rev[K_][N_]; ll sq(ll a) { return a * a; } deque<int> deq; int main() { scanf("%d%d", &N, &K); ++K; for (int i = 1; i <= N; i++) { int x; scanf("%d", &x); S[i] = S[i - 1] + x; } // min sum {s^2} for (int i = 1; i <= N; i++) table[1][i] = sq(S[i]); for (int k = 2; k <= K; k++) { ll *cur = table[k & 1]; ll *prv = table[~k & 1]; for (int i = 1; i <= N; i++) cur[i] = prv[i]; cur[k] = prv[k - 1] + sq(S[k] - S[k - 1]); deq.push_back(k - 1); for (int i = k + 1; i <= N; i++) { // get best { while (deq.size() > 1) { int a = deq[0], b = deq[1]; lf ix = (lf)(prv[b] - prv[a] + sq(S[b]) - sq(S[a])) / (2 * S[b] - 2 * S[a]); if (S[i] <= ix) break; deq.pop_front(); } } // update { int j = deq.front(); cur[i] = (prv[j] + sq(S[j])) - 2 * S[j] * S[i] + sq(S[i]); rev[k][i] = j; } // insert line { while (deq.size() > 1) { int t = *deq.rbegin(); if (S[t] == S[i]) break; int l = *++deq.rbegin(); lf i1 = (lf)(prv[l] - prv[t] + sq(S[l]) - sq(S[t])) / (2 * S[l] - 2 * S[t]); lf i2 = (lf)(prv[i - 1] - prv[t] + sq(S[i - 1]) - sq(S[t])) / (2 * S[i - 1] - 2 * S[t]); if (i1 > i2) deq.pop_back(); else break; } deq.push_back(i - 1); } } } /*for (int k = 2; k <= K; k++) { for (int i = k; i <= N; i++) { // naive printf("tb[%d,%d] = %lld -> ", k,i,table[k][i]); table[k][i] = table[k - 1][i]; for (int j = k - 1; j < i; j++) { ll cur = (table[k - 1][j] + sq(S[j])) - 2 * S[j] * S[i] + sq(S[i]); // ----------------constant -----기울기 ---x좌표 --------상관X table[k][i] = min(table[k][i], cur); } printf("%lld\n", table[k][i]); } }*/ printf("%lld\n", (sq(S[N]) - table[K & 1][N]) / 2); vector<int> rec; for (int i = K, j = N; i > 0;) { if(i < K) rec.push_back(j); j = rev[i--][j]; } reverse(rec.begin(), rec.end()); for (int x : rec) printf("%d ", x); 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...