#include <iostream>
#include <cstdio>
#define taskname "TEST"
using namespace std;
const int maxn = 1e4+3;
const int maxk = 1e2+3;
const long long inf = 1e18 + 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;
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;
}
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;
}
Compilation message
sequence.cpp: In function 'int main()':
sequence.cpp:98:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
98 | freopen(taskname".INP","r",stdin),
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:99:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
99 | freopen(taskname".OUT","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 108 == 108 |
| 2 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 999 == 999 |
| 3 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 0 == 0 |
| 4 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 1542524 == 1542524 |
| 5 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 4500000000 == 4500000000 |
| 6 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 1 == 1 |
| 7 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 1 == 1 |
| 8 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 1 == 1 |
| 9 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 100400096 == 100400096 |
| 10 |
Incorrect |
1 ms |
620 KB |
declared answer doesn't correspond to the split scheme: declared = 900320000, real = 900240000 |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 1093956 == 1093956 |
| 2 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 302460000 == 302460000 |
| 3 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
| 4 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
| 5 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 1005304678 == 1005304678 |
| 6 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 933702 == 933702 |
| 7 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 25082842857 == 25082842857 |
| 8 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 687136 == 687136 |
| 9 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 27295930079 == 27295930079 |
| 10 |
Correct |
1 ms |
640 KB |
contestant found the optimal answer: 29000419931 == 29000419931 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 610590000 == 610590000 |
| 2 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 311760000 == 311760000 |
| 3 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
| 4 |
Correct |
1 ms |
620 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
| 5 |
Incorrect |
1 ms |
620 KB |
declared answer doesn't correspond to the split scheme: declared = 1019625819, real = 718935610 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
620 KB |
contestant found the optimal answer: 21503404 == 21503404 |
| 2 |
Correct |
2 ms |
620 KB |
contestant found the optimal answer: 140412195 == 140412195 |
| 3 |
Correct |
2 ms |
620 KB |
contestant found the optimal answer: 49729674225461 == 49729674225461 |
| 4 |
Correct |
2 ms |
620 KB |
contestant found the optimal answer: 37485571387523 == 37485571387523 |
| 5 |
Incorrect |
3 ms |
620 KB |
declared answer doesn't correspond to the split scheme: declared = 679388326, real = 679308374 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
876 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
| 2 |
Correct |
9 ms |
876 KB |
contestant found the optimal answer: 1326260195 == 1326260195 |
| 3 |
Correct |
9 ms |
876 KB |
contestant found the optimal answer: 4973126687469639 == 4973126687469639 |
| 4 |
Incorrect |
9 ms |
876 KB |
declared answer doesn't correspond to the split scheme: declared = 4502916069783671, real = 2225771185994477 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
748 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
