Submission #216237

#TimeUsernameProblemLanguageResultExecution timeMemory
216237GiantpizzaheadSplit the sequence (APIO14_sequence)Java
0 / 100
299 ms33668 KiB
/* * The order of the splits does not matter (figure this out by trying smaller cases). * Use some algebra to transform the cost into a more workable form. * ab + ac + bc = [(a + b + c)^2 - (a^2 + b^2 + c^2)] / 2 * (a + b + c) remains constant, so the goal is to find the best way to split the array into pieces a, b, c such that * the sum of the squares is minimized. This can be done using dynamic programming, with a form of convex hull optimization. * Runtime: O(NK) */ import java.util.*; import java.io.*; public class sequence { final long INF = 5876543212345678L; int N, K; int[] arr; int[][] from; ConvexHull hull; sequence(BufferedReader in, PrintWriter out) throws IOException { StringTokenizer st = new StringTokenizer(in.readLine()); N = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken()) + 1; arr = new int[N]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken()); hull = new ConvexHull(); from = new int[K + 1][N + 1]; long[][] dp = new long[2][N + 1]; Arrays.fill(dp[0], INF); dp[0][0] = 0; int currDP = 1; for (int i = 1; i <= K; i++) { hull.bot = 0; hull.top = 0; int currX = 0; for (int j = 0; j <= N; j++) { // Transition from best state State s = hull.query(currX); if (s == null) dp[currDP][j] = INF; else { dp[currDP][j] = s.eval(currX); from[i][j] = s.i; } // Add new transition if (dp[1-currDP][j] != INF) hull.add(new State(currX, dp[1-currDP][j], j)); // Move currX if (j != N) currX += arr[j]; } // System.out.println(Arrays.toString(dp[currDP])); // System.out.println(Arrays.toString(from[i])); currDP = 1 - currDP; } out.println(dp[1-currDP][N]); int loc = N; for (int i = K; i > 1; i--) { loc = from[i][loc]; if (i != K) out.print(' '); out.print(loc); } out.println(); } class ConvexHull { State[] states; int bot, top; ConvexHull() { states = new State[N]; bot = 0; top = 0; } void add(State s) { // Remove states with the same sx while (top - bot >= 2 && states[top-1].sx == s.sx) { if (states[top-1].sy > s.sy) top--; else return; // This state is useless } // Remove useless states while (top - bot >= 2) { State prev = states[top-1]; State prev2 = states[top-2]; if (prev2.intersect(prev) >= prev.intersect(s)) { // prev is useless top--; } else break; } // Add this state states[top++] = s; } /** * Assumes x is in increasing order. */ State query(int x) { // Remove outdated states while (top - bot >= 2) { if (states[bot].eval(x) >= states[bot+1].eval(x)) { // Bottom state is outdated bot++; } else break; } if (top - bot == 0) return null; return states[bot]; } } class State { int sx, i; long sy; State(int sx, long sy, int i) { this.sx = sx; this.sy = sy; this.i = i; } double intersect(State o) { double part1 = (sy - o.sy) / (2 * (sx - o.sx)); double part2 = (sx + o.sx) / 2; return part1 + part2; } long eval(int x) { return sy + (long) (sx - x) * (sx - x); } } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); new sequence(in, out); in.close(); out.close(); } }
#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...