제출 #977548

#제출 시각아이디문제언어결과실행 시간메모리
977548josanneo22수열 (APIO14_sequence)C++17
0 / 100
10 ms7000 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; using i64 = long long; #define L(i, j, k) for (int i = (j); i <= (k); ++i) #define R(i, j, k) for (int i = (j); i >= (k); --i) #define all(x) x.begin(), x.end() const int nax = 100050; const int kax = 204; int N, K; int a[nax]; int from[kax][nax]; i64 dp[2][nax]; i64 pre[nax]; int q[nax]; int L = 1, R = 1; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N >> K; L(i, 1, N) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; } L(i, 0, N) dp[0][i] = 0; L(k, 1, K) { q[R++] = 0; int nw = k & 1; int pv = nw ^ 1; auto Y = [&](int x) { return dp[pv][x]; }; auto X = [&](int x) { return pre[x]; }; auto dY = [&](int x, int y) { return Y(x) - Y(y); }; auto dX = [&](int x, int y) { return X(x) - X(y); }; auto DP = [&](int x, int y) { return dp[pv][y] + (pre[x] - pre[y]) * (pre[N] - pre[x]); }; L(i, 1, N) { while (R - L > 1 && dY(q[L + 1], q[L]) >= (pre[N] - pre[i]) * dX(q[L + 1], q[L])) L++; int j = q[L]; dp[nw][i] = DP(i, j); from[k][i] = j; while (R - L > 1 && dY(i, q[R - 1]) * dX(q[R - 1], q[R - 2]) >= dY(q[R - 1], q[R - 2]) * dX(i, q[R - 1])) R--; q[R++] = i; } L(i, 1, N) dp[pv][i] = 0; L = R = 1; } i64 mx = -1; int start = -1; L(i, 1, N) { if (mx <= dp[N & 1][i]) { mx = dp[N & 1][i]; start = i; } } cout << mx << '\n'; L(i, 0, K - 1) { cout << start << ' '; start = from[K - i][start]; } } /* contribution = sum in segment * sum after the segment dp[i][j] = considered until i and have j splits for all p < i dp[i][j] = max(dp[p][j - 1] + (pre[i] - pre[p]) * (pre[N] - pre[i])) dp[i][j] = max(dp[p][j - 1] + - pre[p] * (pre[N] - pre[i])) + (pre[i]) * (pre[N] - pre[i]) m = -pre[p] x = pre[N] - pre[i] c = dp[p][j - 1] CHT: if x is better than y: dp[x][j - 1] - pre[x] * (pre[N] - pre[i]) >= dp[y][j - 1] - pre[y] * (pre[N] - pre[i]) dp[x][j - 1] - dp[y][j - 1] >= (pre[x] - pre[y]) * (pre[N] - pre[i]) Y(x) = dp[x] X(x) = pre[x] Y(x) - (y) >= (X(x) - X(y)) * (pre[N] - pre[i]) slope(i, q[r]) <= slope(q[r], q[r - 1]) pop */
#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...