oj.uz

답안 #216245

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
216245 2020-03-27T00:31:28 Z Giantpizzahead 수열 (APIO14_sequence) Java 11
100 / 100
 1502 ms 119540 KB 
/*
 * 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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 10388 KB contestant found the optimal answer: 108 == 108
2 Correct 78 ms 10508 KB contestant found the optimal answer: 999 == 999
3 Correct 85 ms 10364 KB contestant found the optimal answer: 0 == 0
4 Correct 82 ms 10488 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 74 ms 10600 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 77 ms 10420 KB contestant found the optimal answer: 1 == 1
7 Correct 80 ms 10484 KB contestant found the optimal answer: 1 == 1
8 Correct 77 ms 10364 KB contestant found the optimal answer: 1 == 1
9 Correct 78 ms 10360 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 77 ms 10524 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 77 ms 10488 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 90 ms 10640 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 79 ms 10488 KB contestant found the optimal answer: 140072 == 140072
14 Correct 75 ms 10360 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 78 ms 10472 KB contestant found the optimal answer: 805 == 805
16 Correct 77 ms 10480 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 75 ms 10340 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 10528 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 85 ms 10236 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 101 ms 10652 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 77 ms 10616 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 83 ms 10604 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 82 ms 10484 KB contestant found the optimal answer: 933702 == 933702
7 Correct 82 ms 10504 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 82 ms 10380 KB contestant found the optimal answer: 687136 == 687136
9 Correct 78 ms 10484 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 82 ms 10600 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 10508 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 85 ms 10436 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 103 ms 11256 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 85 ms 10360 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 101 ms 11268 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 102 ms 11880 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 106 ms 11660 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 89 ms 11068 KB contestant found the optimal answer: 193556962 == 193556962
9 Correct 89 ms 10744 KB contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 88 ms 10724 KB contestant found the optimal answer: 490686959791 == 490686959791

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 10868 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 91 ms 10756 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 137 ms 12384 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 97 ms 10664 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 139 ms 13284 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 142 ms 12408 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 151 ms 12276 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 140 ms 12732 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 114 ms 12148 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 134 ms 12156 KB contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 14220 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 177 ms 14200 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Correct 311 ms 22844 KB contestant found the optimal answer: 4973126687469639 == 4973126687469639
4 Correct 170 ms 14800 KB contestant found the optimal answer: 3748491676694116 == 3748491676694116
5 Correct 379 ms 20204 KB contestant found the optimal answer: 1085432199 == 1085432199
6 Correct 311 ms 21004 KB contestant found the optimal answer: 514790755404 == 514790755404
7 Correct 316 ms 22304 KB contestant found the optimal answer: 1256105310476641 == 1256105310476641
8 Correct 293 ms 19984 KB contestant found the optimal answer: 3099592898816 == 3099592898816
9 Correct 322 ms 20720 KB contestant found the optimal answer: 1241131419367412 == 1241131419367412
10 Correct 322 ms 22764 KB contestant found the optimal answer: 1243084101967798 == 1243084101967798

Subtask #6
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 27392 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 302 ms 27596 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Correct 1502 ms 117088 KB contestant found the optimal answer: 497313449256899208 == 497313449256899208
4 Correct 308 ms 31148 KB contestant found the optimal answer: 374850090734572421 == 374850090734572421
5 Correct 1449 ms 119540 KB contestant found the optimal answer: 36183271951 == 36183271951
6 Correct 1296 ms 118996 KB contestant found the optimal answer: 51629847150471 == 51629847150471
7 Correct 1332 ms 117788 KB contestant found the optimal answer: 124074747024496432 == 124074747024496432
8 Correct 887 ms 71736 KB contestant found the optimal answer: 309959349080800 == 309959349080800
9 Correct 1156 ms 117980 KB contestant found the optimal answer: 124113525649823701 == 124113525649823701
10 Correct 1478 ms 118532 KB contestant found the optimal answer: 124309619349406845 == 124309619349406845