제출 #332497

#제출 시각아이디문제언어결과실행 시간메모리
332497KWang31수열 (APIO14_sequence)Java
60 / 100
700 ms131072 KiB
//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<>(); ind=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--) { cur=ch[cur][i];arl.add(cur); } 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); //System.out.println(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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...