제출 #672593

#제출 시각아이디문제언어결과실행 시간메모리
672593garam1732수열 (APIO14_sequence)C++14
0 / 100
61 ms131072 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define blank " " #define endl "\n" typedef long long ll; typedef pair<int, int> pi; typedef pair<int, pi> pii; typedef pair<ll, ll> pll; const int MAXN = 100100; const int MOD = 1e9+7; struct Line { ll a, b; double c; int t; }; double cross(Line x, Line y) { if(x.a != y.a) return (double)(y.b-x.b)/(x.a-y.a); if(x.b > y.b) return LLONG_MIN; return LLONG_MAX; } ll sum[MAXN], dp[MAXN][220]; int idx[MAXN][220]; vector<Line> v; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; for(int i = 1; i <= n; i++) { int a; cin >> a; sum[i] = sum[i-1] + a; } for(int i = 1; i <= n; i++) dp[i][1] = sum[i]*sum[i]; // for(int j = 2; j <= k+1; j++) { // int piv = 0; // v.clear(); // for(int i = j; i <= n; i++) { // Line g = {-2*sum[i-1], sum[i-1]*sum[i-1]+dp[i-1][j-1], 0, i-1}; // while(v.size() && (g.c = cross(*v.rbegin(), g)) < v.rbegin()->c) v.pop_back(); // if(v.empty() || v.rbegin()->a != g.a) v.push_back(g); // // piv = min(piv, (int)v.size()-1); // while(piv+1 < v.size() && v[piv+1].c < sum[i]) piv++; // dp[i][j] = sum[i]*sum[i] + v[piv].a*sum[i] + v[piv].b; // idx[i][j] = v[piv].t; // } // } cout << (sum[n]*sum[n] - dp[n][k+1])/2 << endl; for(int i = idx[n][k+1]; k; i = idx[i][k--]) cout << i << blank; }
#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...