# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
23166 | 2017-05-04T06:14:44 Z | ruhanhabib39 | 수열 (APIO14_sequence) | C++14 | 13 ms | 91876 KB |
#include <bits/stdc++.h> using namespace std; typedef long long Long; const int MAXN = 1e5; const int MAXK = 200; int N, K; Long A[MAXN + 10], S[MAXN + 10]; Long dp[2][MAXN + 10]; int pos[MAXK + 10][MAXN + 10]; struct dat { Long m, b; int i; Long f(Long x) const { return m*x + b; } }; bool bad(dat l1, dat l2, dat l3) { return (l1.b - l2.b)*(l3.m - l1.m) > (l1.b - l3.b)*(l2.m - l1.m); } vector<dat> L; void add(dat l) { L.push_back(l); while(L.size() >= 3 && bad(L[L.size()-3], L[L.size()-2], L[L.size()-1])) { L.erase(L.end() - 2); } } int ii = 0; int get(Long x) { if(ii >= (int)L.size()) ii = L.size()-1; while(ii+1 < (int)L.size() && L[ii+1].f(x) > L[ii].f(x)) { ii++; } return L[ii].i; } void add(int x, int j) { Long m = S[j]; Long b = - S[j] * S[j] + dp[x][j]; add(dat{m, b, j}); } void calc_dp() { for(int k = 1; k <= K; k++) { int x = k & 1; L.clear(); ii = 0; if(k > 0) add(x ^ 1, k-1); for(int i = k; i <= N; i++) { int j = get(S[i]); pos[k][i] = j; dp[x][i] = S[j]*S[i] - S[j]*S[j] + dp[x^1][j]; add(x ^ 1, i); } } } int main() { scanf("%d%d", &N, &K); S[0] = 0; for(int i = 1; i <= N; i++) { scanf("%lld", &A[i]); S[i] = A[i] + S[i-1]; } calc_dp(); printf("%lld\n", dp[K&1][N]); int i = N, k = K; while(k > 0) { i = pos[k][i]; printf("%d ", i); k--; } printf("\n"); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 87184 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 0 ms | 87184 KB | contestant found the optimal answer: 999 == 999 |
3 | Incorrect | 0 ms | 87184 KB | Integer 0 violates the range [1, 1] |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 87184 KB | contestant didn't find the optimal answer: 252308 < 1093956 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 87184 KB | Integer 0 violates the range [1, 199] |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 87184 KB | Integer 0 violates the range [1, 999] |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 87844 KB | contestant didn't find the optimal answer: 1187850 < 1818678304 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 13 ms | 91876 KB | contestant didn't find the optimal answer: 5054352 < 19795776960 |
2 | Halted | 0 ms | 0 KB | - |