제출 #23310

#제출 시각아이디문제언어결과실행 시간메모리
23310Nurlykhan수열 (APIO14_sequence)C++14
0 / 100
1139 ms25924 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define f first #define s second #define pb push_back #define mp make_pair #define ll long long #define ld long double #define sz(v) int(v.size()) #define all(v) v.begin(), v.end() using namespace std; const int N = (int) 1e4 + 7; const int M = (int) 2e6 + 7; const int K = 202; const ll LINF = (ll) 1e18; const int INF = (int) 1e9 + 7; const double EPS = (double) 1e-9; ll dp[N][K], a[N]; int p[N][K]; int n, k; ll sum(int l, int r) { return a[r] - a[l - 1]; } ld inter(int i, int x, int y) { return (dp[y][i] - dp[x][i]) * 1.0 / (a[y] - a[x]); } vector<int> st; int f(int i, int j, int x) { return x * a[i] + dp[i][j]; } int get(int j, int x) { int id = 0; for (auto it : st) { if (f(it, j, x) > f(id, j, x)) id = it; } return id; } int main() { #define fn "balls" #ifdef witch freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else // freopen(fn".in", "r", stdin); // freopen(fn".out", "w", stdout); #endif cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] += a[i - 1]; } for (int i = 1; i <= n; i++) { dp[i][1] = sum(1, i) * sum(i + 1, n); } for (int i = 2; i <= k; i++) { st.clear(); for (int j = 1; j <= n; j++) { while (sz(st) > 1 && inter(i - 1, st[sz(st) - 2], st[sz(st) - 1]) < inter(i - 1, st[sz(st) - 1], j)) { st.pop_back(); } /* y[t] = (a[j] - a[t]) * (a[n] - a[j]) + dp[t][i - 1] a[j]*a[n]-a[j]*a[j]-a[t]*a[n]+a[t]*a[j] a[t]*(-a[n]+a[j])+dp[t][i-1]+a[j]*(a[n]-a[j]) k=a[j]-a[t] */ if (!st.empty()) { int t = get(i - 1, -sum(j + 1, n)); dp[j][i] = dp[t][i - 1] + sum(j + 1, n) * sum(t + 1, j); p[j][i] = t; } st.pb(j); } } int j = 1; for (int i = 1; i <= n; i++) { if (dp[j][k] < dp[i][k]) j = i; } cout << dp[j][k] << endl; vector<int> ans; while (j > 0 && k > 0) { ans.pb(j); j = p[j][k]; k--; } reverse(all(ans)); for (auto it : ans) cout << it << " "; 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...