제출 #15747

#제출 시각아이디문제언어결과실행 시간메모리
15747conankun수열 (APIO14_sequence)C++98
0 / 100
0 ms131072 KiB
#include<iostream> #include<vector> #include<algorithm> typedef long long ll; using namespace std; ll S[111111]; ll D[202][111111]; int bt[202][111111]; int N, K; long double g(int k, int a, int b) { return (long double)(D[k - 1][b] - D[k - 1][a] - S[b] * S[b] + S[a] * S[a]) / (S[a]-S[b]); } inline ll max(ll a, ll b) { if (a > b) return a; return b; } int qu[111111]; int main() { cin.sync_with_stdio(false); cin >> N >> K; int i,j, k; for (i = 1; i <= N; i++) { cin >> S[i]; S[i] += S[i - 1]; } for (k = 1; k <= K; k++) { int s = 0, e = 0; for (i = 1; i <= N; i++) { for (j = s; j <= e-1; j++) { if (g(k, qu[j], qu[j + 1]) < S[i]) s++; else break; } j = qu[s]; D[k][i] = D[k - 1][j] + S[j] * (S[i] - S[j]); bt[k][i] = j; for (j = e; j > s; j--) { if (g(k, qu[j], qu[j - 1]) >= g(k, qu[j - 1], i)) { e--; } else break; } qu[++e] = i; } } ll ans = D[K][N]; cout << ans << endl; k = K; i = N; vector<int> btans; while (bt[k][i] != 0) { btans.push_back(bt[k][i]); i = bt[k][i]; k--; } sort(btans.begin(), btans.end()); k = btans.size(); for (i = 0; i < k; i++) { cout << btans[i] << " "; } }
#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...