제출 #216245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216245		Giantpizzahead	수열 (APIO14_sequence)	Java	100 / 100	1502 ms	119540 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(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];
            for (int i = 0; i < N; i++) states[i] = new State(-1, -1, -1);
            bot = 0;
            top = 0;
        }

        void add(int sx, long sy, int i) {
            // Remove states with the same sx
            while (top - bot >= 2 && states[top-1].sx == sx) {
                if (states[top-1].sy > 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(sx, sy)) {
                    // prev is useless
                    top--;
                } else break;
            }

            // Add this state
            states[top].sx = sx;
            states[top].sy = sy;
            states[top++].i = i;
        }

        /**
         * 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) {
            return intersect(o.sx, o.sy);
        }

        double intersect(int osx, long osy) {
            double part1 = (sy - osy) / (2 * (sx - osx));
            double part2 = (sx + osx) / 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: 29 / 29