This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//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<Long> M=new ArrayList<>();
static ArrayList<Long> B=new ArrayList<>();
static ArrayList<Integer> ind=new ArrayList<>();
static int pointer=0;
static int[][] ch;
static int N;
public static void main(String[] args){
FastReader br=new FastReader();
N=br.nextInt(); int K=br.nextInt();
long[] s=new long[N];
long[] dp=new long[N];
long[] dp2=new long[N];
ch=new int[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 ArrayList<>();
add(s[0],-s[0]*s[0],i);
for (int j = 1; j < N; j++) {
dp2[j]=query(s[j],N*i+j);
add(s[j],dp[j]-s[j]*s[j],j);
//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--) {
arl.add(ch[cur][i]); cur=ch[cur][i];
}
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.get(l2)-B.get(l1))>(M.get(l1)-M.get(l2))*((double)B.get(l3)-B.get(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(long m, long b, int i){
M.add(m); B.add(b); ind.add(i);
while(M.size()>=3 && bad(M.size()-3,M.size()-2,M.size()-1)){
M.remove(M.size()-2); B.remove(B.size()-2); 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.get(pointer+1) >M.get(pointer)*x+B.get(pointer)){
pointer++;
}
ch[j%N][j/N]=ind.get(pointer);
return M.get(pointer)*x+B.get(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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |