//Convex Hull Trick, verified on CF319C (319 is ID)
import java.io.*; import java.util.*;
public class sequence{
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
}
static ArrayList<Integer> M=new ArrayList<>();
static long[] B;
static ArrayList<Integer> ind=new ArrayList<>();
static int pointer=0;
static short[][] ch; static boolean[][] b1; static boolean[][] b2;
static int N;
public static void main(String[] args){
FastReader br=new FastReader();
N=br.nextInt(); int K=br.nextInt();
int[] s=new int[N];
long[] dp=new long[N];
long[] dp2=new long[N];
ch=new short[N][K]; b1=new boolean[N][K];b2=new boolean[N][K];
s[0]=br.nextInt(); for(int i=1;i<N;i++){s[i]=s[i-1]+br.nextInt(); }
//System.out.println(Arrays.toString(s));
for (int i = 0; i < K; i++) {
M=new ArrayList<>();
B=new long[N];
ind=new ArrayList<>();
add(s[0],-(long)s[0]*s[0],i);
for (int j = 1; j < N; j++) {
dp2[j]=query((long)s[j],N*i+j);
add(s[j], dp[j]-(long)s[j]*s[j],Math.max(j,i));
//System.out.println(M);
//System.out.println(B);
}
for (int j = 0; j < N; j++) {
dp[j]=dp2[j];
}
//System.out.println(Arrays.toString(dp));
}
//System.out.println(Arrays.toString(dp));
System.out.println(dp[N-1]);
StringBuilder sb=new StringBuilder();
ArrayList<Integer> arl=new ArrayList<>();
int cur=N-1;
for (int i = K-1; i >=0; i--) {
if(b1[cur][i] && b2[cur][i])cur=(int) 4*ch[cur][i]+3;
else if(b1[cur][i]) cur=(int) 4*ch[cur][i]+1;
else if(b2[cur][i]) cur=(int) 4*ch[cur][i]+2;
else cur=(int) 4*ch[cur][i];
arl.add(cur);
}
//StringBuilder is actually quite memory consuming
for (int i = K-1; i >=0; i--) {
sb.append((arl.get(i)+1)+" ");
}
System.out.println(sb.toString());
}
public static boolean bad(int l1, int l2, int l3){//Using doubles to prevent overflow
return (M.get(l1)-M.get(l3))*((double)B[l2]-B[l1])>=(M.get(l1)-M.get(l2))*((double)B[l3]-B[l1]);
//Intersection of l1 and l3 must be ABOVE l2
//For l2 to be added
//l1.m>l2.m>l3.m, as sum is strictly increasing
}
public static void add(int m, long b, int i){
M.add(m); B[ind.size()]=b; ind.add(i);
while(M.size()>=3 && bad(M.size()-3,M.size()-2,M.size()-1)){
M.remove(M.size()-2); B[ind.size()-2]=b; ind.remove(ind.size()-2);
}
}
public static long query(long x, int j){
if(pointer>=M.size()){pointer=M.size()-1;}
while(pointer<M.size()-1 &&
M.get(pointer+1)*x+B[pointer+1] > M.get(pointer)*x+B[pointer]){
pointer++;
}
ch[j%N][j/N]=(short)(ind.get(pointer)/4);
if(ind.get(pointer)%2==1){
b1[j%N][j/N]=true;
}
if(ind.get(pointer)%4>=2){
b2[j%N][j/N]=true;
}
return M.get(pointer)*x+B[pointer];
}
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
9960 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
113 ms |
9580 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Correct |
111 ms |
9708 KB |
contestant found the optimal answer: 0 == 0 |
4 |
Correct |
113 ms |
9580 KB |
contestant found the optimal answer: 1542524 == 1542524 |
5 |
Correct |
109 ms |
9580 KB |
contestant found the optimal answer: 4500000000 == 4500000000 |
6 |
Correct |
109 ms |
9580 KB |
contestant found the optimal answer: 1 == 1 |
7 |
Correct |
113 ms |
9600 KB |
contestant found the optimal answer: 1 == 1 |
8 |
Correct |
110 ms |
9580 KB |
contestant found the optimal answer: 1 == 1 |
9 |
Correct |
110 ms |
9708 KB |
contestant found the optimal answer: 100400096 == 100400096 |
10 |
Correct |
120 ms |
9688 KB |
contestant found the optimal answer: 900320000 == 900320000 |
11 |
Correct |
113 ms |
9536 KB |
contestant found the optimal answer: 3698080248 == 3698080248 |
12 |
Correct |
111 ms |
9600 KB |
contestant found the optimal answer: 3200320000 == 3200320000 |
13 |
Correct |
110 ms |
9580 KB |
contestant found the optimal answer: 140072 == 140072 |
14 |
Correct |
111 ms |
9452 KB |
contestant found the optimal answer: 376041456 == 376041456 |
15 |
Correct |
115 ms |
9580 KB |
contestant found the optimal answer: 805 == 805 |
16 |
Correct |
110 ms |
9580 KB |
contestant found the optimal answer: 900189994 == 900189994 |
17 |
Correct |
112 ms |
9572 KB |
contestant found the optimal answer: 999919994 == 999919994 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
9580 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Correct |
120 ms |
9700 KB |
contestant found the optimal answer: 302460000 == 302460000 |
3 |
Correct |
145 ms |
9776 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
4 |
Correct |
115 ms |
9580 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
5 |
Correct |
123 ms |
9580 KB |
contestant found the optimal answer: 1005304678 == 1005304678 |
6 |
Correct |
119 ms |
9448 KB |
contestant found the optimal answer: 933702 == 933702 |
7 |
Correct |
130 ms |
9680 KB |
contestant found the optimal answer: 25082842857 == 25082842857 |
8 |
Correct |
121 ms |
9580 KB |
contestant found the optimal answer: 687136 == 687136 |
9 |
Correct |
115 ms |
9580 KB |
contestant found the optimal answer: 27295930079 == 27295930079 |
10 |
Correct |
116 ms |
9708 KB |
contestant found the optimal answer: 29000419931 == 29000419931 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
9472 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
122 ms |
9576 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
223 ms |
13976 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Correct |
123 ms |
9580 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 |
Correct |
230 ms |
14052 KB |
contestant found the optimal answer: 1019625819 == 1019625819 |
6 |
Correct |
235 ms |
14252 KB |
contestant found the optimal answer: 107630884 == 107630884 |
7 |
Correct |
233 ms |
14076 KB |
contestant found the optimal answer: 475357671774 == 475357671774 |
8 |
Correct |
178 ms |
11720 KB |
contestant found the optimal answer: 193556962 == 193556962 |
9 |
Correct |
165 ms |
10264 KB |
contestant found the optimal answer: 482389919803 == 482389919803 |
10 |
Correct |
211 ms |
12928 KB |
contestant found the optimal answer: 490686959791 == 490686959791 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
146 ms |
9932 KB |
contestant found the optimal answer: 21503404 == 21503404 |
2 |
Correct |
158 ms |
10088 KB |
contestant found the optimal answer: 140412195 == 140412195 |
3 |
Correct |
243 ms |
14760 KB |
contestant found the optimal answer: 49729674225461 == 49729674225461 |
4 |
Correct |
145 ms |
9944 KB |
contestant found the optimal answer: 37485571387523 == 37485571387523 |
5 |
Correct |
260 ms |
15112 KB |
contestant found the optimal answer: 679388326 == 679388326 |
6 |
Correct |
259 ms |
14984 KB |
contestant found the optimal answer: 4699030287 == 4699030287 |
7 |
Correct |
253 ms |
15232 KB |
contestant found the optimal answer: 12418819758185 == 12418819758185 |
8 |
Correct |
269 ms |
15464 KB |
contestant found the optimal answer: 31093317350 == 31093317350 |
9 |
Correct |
232 ms |
13872 KB |
contestant found the optimal answer: 12194625429236 == 12194625429236 |
10 |
Correct |
241 ms |
14512 KB |
contestant found the optimal answer: 12345131038664 == 12345131038664 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
459 ms |
18416 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
2 |
Correct |
463 ms |
18332 KB |
contestant found the optimal answer: 1326260195 == 1326260195 |
3 |
Correct |
708 ms |
27896 KB |
contestant found the optimal answer: 4973126687469639 == 4973126687469639 |
4 |
Correct |
434 ms |
17408 KB |
contestant found the optimal answer: 3748491676694116 == 3748491676694116 |
5 |
Correct |
676 ms |
24916 KB |
contestant found the optimal answer: 1085432199 == 1085432199 |
6 |
Correct |
667 ms |
26208 KB |
contestant found the optimal answer: 514790755404 == 514790755404 |
7 |
Correct |
707 ms |
26908 KB |
contestant found the optimal answer: 1256105310476641 == 1256105310476641 |
8 |
Correct |
618 ms |
25156 KB |
contestant found the optimal answer: 3099592898816 == 3099592898816 |
9 |
Correct |
654 ms |
25784 KB |
contestant found the optimal answer: 1241131419367412 == 1241131419367412 |
10 |
Correct |
698 ms |
27704 KB |
contestant found the optimal answer: 1243084101967798 == 1243084101967798 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
618 ms |
43152 KB |
contestant found the optimal answer: 19795776960 == 19795776960 |
2 |
Correct |
621 ms |
43132 KB |
contestant found the optimal answer: 19874432173 == 19874432173 |
3 |
Runtime error |
639 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |