This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ryan bear
#define sq(X) ((X)*(X))
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
#define unq(V) (V).erase(unique(all(V)), (V).end())
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = (1ll<<60);
int N, K; vlm ar; ll mx; int mi; int lst[205][100010];
struct line {
ll a, b; int ind;
ll get(ll x) { return a*x+b; }
line() {}
line(ll A, ll B, int i) { a=A, b=B, ind=i; }
};
struct LiChao {
int l[100010], r[100010], tp;
line L[100010];
inline void init() { memset(l, 0, sizeof(l)); memset(r, 0, sizeof(r)); tp=2; L[0]=L[1]=line(0, -INF, 0); }
inline void upd(int now, line &v, ll s, ll e) {
ll md=(s+e)/2;
line lo=L[now], hi=v;
if (lo.get(s)>hi.get(s)) swap(lo, hi);
if (lo.get(e)<=hi.get(e)) { L[now]=hi; return ; }
if (lo.get(md)>=hi.get(md)) {
L[now]=lo;
if (!l[now]) { l[now]=tp; tp++; }
upd(l[now], hi, s, md);
}
else {
L[now]=hi;
if (!r[now]) { r[now]=tp; L[tp]=line(0, -INF, 0); tp++; }
upd(r[now], lo, md+1, e);
}
}
inline pll get(int now, ll x, ll s, ll e) {
if (!now) return pll(-INF, 0);
ll md=(s+e)/2;
if (x<=md) return max(pll(L[now].get(x), L[now].ind), get(l[now], x, s, md));
else return max(pll(L[now].get(x), L[now].ind), get(r[now], x, md+1, e));
}
}lct[2];
void dfs(int k, int i) {
if (!k) return ;
dfs(k-1, lst[k][i]);
printf("%d ", i);
}
int main() {
scanf("%d %d", &N, &K); ar.resize(N+1);
for (int i=1; i<=N; i++) { scanf("%lld", &ar[i]); ar[i]+=ar[i-1]; }
line im=line(ar[N], 0, 0);
lct[0].init(); lct[0].upd(1, im, 0, ar[N]);
for (int i=1; i<K; i++) {
lct[i&1].init();
for (int j=i; j<N; j++) {
auto k=lct[(i-1)&1].get(1, ar[j], 0, ar[N]); k.fi-=ar[j]*ar[j];
lst[i][j]=k.se;
im=line(ar[N]+ar[j], k.fi-ar[N]*ar[j], j);
lct[i&1].upd(1, im, 0, ar[N]);
}
}
for (int i=K; i<N; i++) {
auto k=lct[(K-1)&1].get(1, ar[i], 0, ar[N]);
lst[K][i]=min(k.se, i-1);
if (mx<=k.fi-ar[i]*ar[i]) mx=k.fi-ar[i]*ar[i], mi=i;
}
printf("%lld\n", mx);
dfs(K, mi); puts("");
return 0;
}
Compilation message (stderr)
sequence.cpp: In function 'int main()':
sequence.cpp:79:26: error: no matching function for call to 'min(long long int&, int)'
lst[K][i]=min(k.se, i-1);
^
In file included from /usr/include/c++/7/bits/specfun.h:45:0,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from sequence.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
min(const _Tp& __a, const _Tp& __b)
^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: template argument deduction/substitution failed:
sequence.cpp:79:26: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
lst[K][i]=min(k.se, i-1);
^
In file included from /usr/include/c++/7/bits/specfun.h:45:0,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from sequence.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
min(const _Tp& __a, const _Tp& __b, _Compare __comp)
^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: template argument deduction/substitution failed:
sequence.cpp:79:26: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
lst[K][i]=min(k.se, i-1);
^
In file included from /usr/include/c++/7/algorithm:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
from sequence.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
min(initializer_list<_Tp> __l)
^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: template argument deduction/substitution failed:
sequence.cpp:79:26: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
lst[K][i]=min(k.se, i-1);
^
In file included from /usr/include/c++/7/algorithm:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
from sequence.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
min(initializer_list<_Tp> __l, _Compare __comp)
^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: template argument deduction/substitution failed:
sequence.cpp:79:26: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
lst[K][i]=min(k.se, i-1);
^
sequence.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &K); ar.resize(N+1);
~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:65:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i=1; i<=N; i++) { scanf("%lld", &ar[i]); ar[i]+=ar[i-1]; }
~~~~~^~~~~~~~~~~~~~~~