Submission #672590

#TimeUsernameProblemLanguageResultExecution timeMemory
672590garam1732Split the sequence (APIO14_sequence)C++14
0 / 100
56 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; }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:42:13: warning: unused variable 'piv' [-Wunused-variable]
   42 |         int piv = 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...