Submission #216240

#	Time	Username	Problem	Language	Result	Execution time	Memory
216240		Giantpizzahead	Split the sequence (APIO14_sequence)	Java	71 / 100	560 ms	131072 KiB

sequence

/*
 * 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;
        }

        long answer = 0;
        for (int i = 0; i < N; i++) answer += arr[i];
        answer *= answer;
        answer -= dp[1-currDP][N];
        answer /= 2;
        out.println(answer);
        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();
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29