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>
using namespace std;
typedef long long int lld;
#define MAX 101010
#define ln '￦n'
lld arr[MAX], dp[MAX], p[MAX], s[MAX], ans[MAX];
int path[MAX][202];
void f(lld ind, lld l, lld r, lld low, lld high){
if(l>r||low>high) return;
lld i, mid=(l+r)/2, mini=mid-1;
dp[mid]=0;
for(i=max(low, ind-1);i<=min(high, mid-1);i++){
if(dp[mid]<p[i]+s[i]*(s[mid]-s[i])){
dp[mid]=p[i]+s[i]*(s[mid]-s[i]);
mini=i;
}
}
path[mid][ind]=(int)mini;
f(ind, l, mid-1, low, mini);
f(ind, mid+1, r, mini, high);
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
lld N, K;
cin>>N>>K;
lld i;
for(i=1;i<=N;i++){
cin>>arr[i];
s[i]=arr[i]+s[i-1];
}
int j;
for(i=2;i<=K+1;i++){
f(i, 1, N, 1, N);
for(j=1;j<=N;j++){
p[j]=dp[j];
}
}
cout<<dp[i]<<ln;
for(i=K+1;i>=2;i--){
ans[i]=(lld)path[N][i];
N=(lld)path[N][i];
}
for(i=2;i<=K+1;i++){
cout<<ans[i]<<ln;
}
return 0;
}
Compilation message (stderr)
sequence.cpp:23:2: error: stray '\302' in program
23 | ios::sync_with_stdio(0);
| ^
sequence.cpp:23:3: error: stray '\240' in program
23 | ios::sync_with_stdio(0);
| ^
sequence.cpp:23:5: error: stray '\302' in program
23 | ios::sync_with_stdio(0);
| ^
sequence.cpp:23:6: error: stray '\240' in program
23 | ios::sync_with_stdio(0);
| ^
sequence.cpp:24:2: error: stray '\302' in program
24 | cin.tie(0);
| ^
sequence.cpp:24:3: error: stray '\240' in program
24 | cin.tie(0);
| ^
sequence.cpp:24:5: error: stray '\302' in program
24 | cin.tie(0);
| ^
sequence.cpp:24:6: error: stray '\240' in program
24 | cin.tie(0);
| ^
sequence.cpp:25:2: error: stray '\302' in program
25 | lld N, K;
| ^
sequence.cpp:25:3: error: stray '\240' in program
25 | lld N, K;
| ^
sequence.cpp:25:5: error: stray '\302' in program
25 | lld N, K;
| ^
sequence.cpp:25:6: error: stray '\240' in program
25 | lld N, K;
| ^
sequence.cpp:26:2: error: stray '\302' in program
26 | cin>>N>>K;
| ^
sequence.cpp:26:3: error: stray '\240' in program
26 | cin>>N>>K;
| ^
sequence.cpp:26:5: error: stray '\302' in program
26 | cin>>N>>K;
| ^
sequence.cpp:26:6: error: stray '\240' in program
26 | cin>>N>>K;
| ^
sequence.cpp:27:2: error: stray '\302' in program
27 | lld i;
| ^
sequence.cpp:27:3: error: stray '\240' in program
27 | lld i;
| ^
sequence.cpp:27:5: error: stray '\302' in program
27 | lld i;
| ^
sequence.cpp:27:6: error: stray '\240' in program
27 | lld i;
| ^
sequence.cpp:29:2: error: stray '\302' in program
29 | cin>>arr[i];
| ^
sequence.cpp:29:3: error: stray '\240' in program
29 | cin>>arr[i];
| ^
sequence.cpp:29:5: error: stray '\302' in program
29 | cin>>arr[i];
| ^
sequence.cpp:29:6: error: stray '\240' in program
29 | cin>>arr[i];
| ^
sequence.cpp:29:8: error: stray '\302' in program
29 | cin>>arr[i];
| ^
sequence.cpp:29:9: error: stray '\240' in program
29 | cin>>arr[i];
| ^
sequence.cpp:29:11: error: stray '\302' in program
29 | cin>>arr[i];
| ^
sequence.cpp:29:12: error: stray '\240' in program
29 | cin>>arr[i];
| ^
sequence.cpp:30:2: error: stray '\302' in program
30 | s[i]=arr[i]+s[i-1];
| ^
sequence.cpp:30:3: error: stray '\240' in program
30 | s[i]=arr[i]+s[i-1];
| ^
sequence.cpp:30:5: error: stray '\302' in program
30 | s[i]=arr[i]+s[i-1];
| ^
sequence.cpp:30:6: error: stray '\240' in program
30 | s[i]=arr[i]+s[i-1];
| ^
sequence.cpp:30:8: error: stray '\302' in program
30 | s[i]=arr[i]+s[i-1];
| ^
sequence.cpp:30:9: error: stray '\240' in program
30 | s[i]=arr[i]+s[i-1];
| ^
sequence.cpp:30:11: error: stray '\302' in program
30 | s[i]=arr[i]+s[i-1];
| ^
sequence.cpp:30:12: error: stray '\240' in program
30 | s[i]=arr[i]+s[i-1];
| ^
sequence.cpp:39:2: error: stray '\302' in program
39 | cout<<dp[i]<<ln;
| ^
sequence.cpp:39:3: error: stray '\240' in program
39 | cout<<dp[i]<<ln;
| ^
sequence.cpp:39:5: error: stray '\302' in program
39 | cout<<dp[i]<<ln;
| ^
sequence.cpp:39:6: error: stray '\240' in program
39 | cout<<dp[i]<<ln;
| ^
sequence.cpp:39:20: warning: multi-character character constant [-Wmultichar]
39 | cout<<dp[i]<<ln;
| ^~
sequence.cpp:40:2: error: stray '\302' in program
40 | for(i=K+1;i>=2;i--){
| ^
sequence.cpp:40:3: error: stray '\240' in program
40 | for(i=K+1;i>=2;i--){
| ^
sequence.cpp:40:5: error: stray '\302' in program
40 | for(i=K+1;i>=2;i--){
| ^
sequence.cpp:40:6: error: stray '\240' in program
40 | for(i=K+1;i>=2;i--){
| ^
sequence.cpp:45:2: error: stray '\302' in program
45 | cout<<ans[i]<<ln;
| ^
sequence.cpp:45:3: error: stray '\240' in program
45 | cout<<ans[i]<<ln;
| ^
sequence.cpp:45:5: error: stray '\302' in program
45 | cout<<ans[i]<<ln;
| ^
sequence.cpp:45:6: error: stray '\240' in program
45 | cout<<ans[i]<<ln;
| ^
sequence.cpp:45:8: error: stray '\302' in program
45 | cout<<ans[i]<<ln;
| ^
sequence.cpp:45:9: error: stray '\240' in program
45 | cout<<ans[i]<<ln;
| ^
sequence.cpp:45:11: error: stray '\302' in program
45 | cout<<ans[i]<<ln;
| ^
sequence.cpp:45:12: error: stray '\240' in program
45 | cout<<ans[i]<<ln;
| ^
sequence.cpp:45:27: warning: multi-character character constant [-Wmultichar]
45 | cout<<ans[i]<<ln;
| ^~
sequence.cpp:46:2: error: stray '\302' in program
46 | }
| ^
sequence.cpp:46:3: error: stray '\240' in program
46 | }
| ^
sequence.cpp:46:5: error: stray '\302' in program
46 | }
| ^
sequence.cpp:46:6: error: stray '\240' in program
46 | }
| ^
sequence.cpp:47:2: error: stray '\302' in program
47 | return 0;
| ^
sequence.cpp:47:3: error: stray '\240' in program
47 | return 0;
| ^
sequence.cpp:47:5: error: stray '\302' in program
47 | return 0;
| ^
sequence.cpp:47:6: error: stray '\240' in program
47 | return 0;
| ^