#include <iostream>
#include <cstdio>
#define taskname "TEST"
using namespace std;
const int maxn = 1e4+3;
const int maxk = 1e2+3;
const long long inf = 1e15 + 7;
struct TLines{
long long a, b;
int id, nArr;
inline TLines(long long _a = 0, long long _b = 0, int _id = 0, int _nArr = 0){
a=_a;
b=_b;
id=_id;
nArr=_nArr;
}
inline long long Value(const long long &x){
return a*x+b;
}
friend inline bool isBad(const TLines &d1, const TLines &d2, const TLines &d3){
return (d2.b-d1.b)*(d1.a-d3.a)>=(d3.b-d1.b)*(d1.a-d2.a);
}
};
int n,k, a[maxn], trace[maxn];
long long s[maxn];
pair<long long, int> f[maxn];
TLines convex[maxn];
inline void Enter(){
cin >> n >> k;
for(int i=1;i<=n;i++) cin >> a[i], s[i] = s[i-1] + a[i];
}
inline pair<long long, int> Calc(const long long &C){ // f[i] = max{ s[j]*s[i] + f[j] - s[j]^2 }
fill(f, f + n + 1, make_pair(0, 0));
fill(trace, trace + n + 1, -1);
int best = 1, nConvex = 0;
convex[++nConvex] = TLines();
f[1] = make_pair(s[1], 1);
for(int i = 1; i <= n; i++){
long long x = s[i];
while(best < nConvex && convex[best].Value(x) <= convex[best + 1].Value(x)) best++;
f[i].first = convex[best].Value(x) - C;
f[i].second = convex[best].nArr + 1;
trace[i] = convex[best].id;
cerr << trace[i] << ' ';
TLines newline(s[i], f[i].first - s[i] * s[i], i, f[i].second);
while(nConvex > 1 && isBad(convex[nConvex - 1], convex[nConvex], newline)){
best -= (best == nConvex);
nConvex--;
}
convex[++nConvex] = newline;
}
cerr << '\n';
return f[n];
// for(int t=1;t<=k;t++){
// int best=1;
// int nConvex=0;
// swap(f,g);
// for(int i=1;i<=n;i++){
// long long x=s[i];
// TLines newline(s[i],g[i]-s[i]*s[i],i);
// while(nConvex>1 && isBad(convex[nConvex-1],convex[nConvex],newline)){
// best-=(best==nConvex);
// nConvex--;
// } convex[++nConvex]=newline;
// while(best<nConvex && convex[best].Value(x)<=convex[best+1].Value(x)) best++;
// f[i]=convex[best].Value(x);
// trace[i][t]=convex[best].id;
// }
// cerr << f[n] - g[n] << ' ';
// }
// cout<<f[n]<<'\n';
// int nG=0;
// for(int x=n,i=k;i>=1;i--) g[++nG]=x=trace[x][i];
// for(int i=nG;i;i--) cout<<g[i]<<' ';
}
inline void Solve(){
long long l = 0, r = inf;
while(l <= r){
long long mid = (l + r) >> 1;
pair<long long, int> res = Calc(mid);
if(res.second >= k + 1) l = mid + 1;
else r = mid - 1;
}
cout << Calc(r).first + (k + 1) * r << '\n';
for(int i = trace[n]; i != 0; i = trace[i]) a[++s[0]] = i;
for(int i = s[0]; i >= 1; i--) cout << a[i] << ' ';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL); if(fopen(taskname".INP","r"))
// freopen(taskname".INP","r",stdin),
// freopen(taskname".OUT","w",stdout);
Enter();
Solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
620 KB |
Integer -1 violates the range [1, 6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
620 KB |
Integer -1 violates the range [1, 49] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
620 KB |
Integer -1 violates the range [1, 199] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
620 KB |
Integer -1 violates the range [1, 999] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
640 KB |
Integer -1 violates the range [1, 9999] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
620 KB |
Integer -1 violates the range [1, 99999] |
| 2 |
Halted |
0 ms |
0 KB |
- |
