Submission #6380881


Source Code Expand

Copy
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.HashMap;
import java.util.Objects;
import java.util.Map;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Egor Kulikov (egor@egork.net)
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        long[] a;
        Map<TaskD.Key, Long> result = new HashMap<>();

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            a = in.readLongArray(n);
            out.printLine(go(0, n - 1, 1, 1) + a[0] + a[n - 1]);
        }

        private long go(int left, int right, long lCoef, long rCoef) {
            TaskD.Key key = new TaskD.Key(left, right, lCoef, rCoef);
            if (left + 1 == right) {
                return 0;
            }
            if (result.containsKey(key)) {
                return result.get(key);
            }
            long answer = Long.MAX_VALUE;
            for (int i = left + 1; i < right; i++) {
                long result = a[i] * (lCoef + rCoef) + go(left, i, lCoef, lCoef + rCoef) + go(i, right, lCoef + rCoef,
                        rCoef);
                answer = Math.min(answer, result);
            }
            result.put(key, answer);
            return answer;
        }

        static class Key {
            int left;
            int right;
            long lCoef;
            long rCoef;

            public Key(int left, int right, long lCoef, long rCoef) {
                this.left = left;
                this.right = right;
                this.lCoef = lCoef;
                this.rCoef = rCoef;
            }

            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (o == null || getClass() != o.getClass()) {
                    return false;
                }
                TaskD.Key key = (TaskD.Key) o;
                return left == key.left &&
                        right == key.right &&
                        lCoef == key.lCoef &&
                        rCoef == key.rCoef;
            }

            public int hashCode() {
                return Objects.hash(left, right, lCoef, rCoef);
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public long[] readLongArray(int size) {
            long[] array = new long[size];
            for (int i = 0; i < size; i++) {
                array[i] = readLong();
            }
            return array;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long readLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(long i) {
            writer.println(i);
        }

    }
}

Submission Info

Submission Time
Task D - Add and Remove
User Egor
Language Java8 (OpenJDK 1.8.0)
Score 1000
Code Size 6284 Byte
Status AC
Exec Time 611 ms
Memory 103908 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 3
AC × 102
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, 73.txt, 74.txt, 75.txt, 76.txt, 77.txt, 78.txt, 79.txt, 80.txt, 81.txt, 82.txt, 83.txt, 84.txt, 85.txt, 86.txt, 87.txt, 88.txt, 89.txt, 90.txt, 91.txt, 92.txt, 93.txt, 94.txt, 95.txt, 96.txt, 97.txt, 98.txt, 99.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 519 ms 103908 KB
02.txt AC 561 ms 98536 KB
03.txt AC 562 ms 100840 KB
04.txt AC 560 ms 101104 KB
05.txt AC 561 ms 101572 KB
06.txt AC 552 ms 99456 KB
07.txt AC 544 ms 101872 KB
08.txt AC 550 ms 100072 KB
09.txt AC 577 ms 102088 KB
10.txt AC 547 ms 99312 KB
11.txt AC 542 ms 99308 KB
12.txt AC 570 ms 100204 KB
13.txt AC 565 ms 100292 KB
14.txt AC 316 ms 62556 KB
15.txt AC 556 ms 99896 KB
16.txt AC 564 ms 100728 KB
17.txt AC 548 ms 100596 KB
18.txt AC 555 ms 100676 KB
19.txt AC 549 ms 102528 KB
20.txt AC 581 ms 99656 KB
21.txt AC 552 ms 100220 KB
22.txt AC 307 ms 63580 KB
23.txt AC 556 ms 101872 KB
24.txt AC 311 ms 65244 KB
25.txt AC 568 ms 102324 KB
26.txt AC 552 ms 100612 KB
27.txt AC 563 ms 99576 KB
28.txt AC 562 ms 98924 KB
29.txt AC 307 ms 62824 KB
30.txt AC 543 ms 101368 KB
31.txt AC 556 ms 99652 KB
32.txt AC 569 ms 100592 KB
33.txt AC 553 ms 103732 KB
34.txt AC 311 ms 62556 KB
35.txt AC 562 ms 98620 KB
36.txt AC 539 ms 99004 KB
37.txt AC 608 ms 101240 KB
38.txt AC 537 ms 99832 KB
39.txt AC 538 ms 100072 KB
40.txt AC 554 ms 102120 KB
41.txt AC 519 ms 97260 KB
42.txt AC 534 ms 96228 KB
43.txt AC 554 ms 100348 KB
44.txt AC 555 ms 98688 KB
45.txt AC 553 ms 100084 KB
46.txt AC 574 ms 99820 KB
47.txt AC 559 ms 102196 KB
48.txt AC 533 ms 101372 KB
49.txt AC 310 ms 65112 KB
50.txt AC 508 ms 103264 KB
51.txt AC 556 ms 101744 KB
52.txt AC 306 ms 61144 KB
53.txt AC 574 ms 102112 KB
54.txt AC 305 ms 63064 KB
55.txt AC 554 ms 99680 KB
56.txt AC 564 ms 100328 KB
57.txt AC 555 ms 98880 KB
58.txt AC 557 ms 101352 KB
59.txt AC 611 ms 98300 KB
60.txt AC 559 ms 101624 KB
61.txt AC 572 ms 98800 KB
62.txt AC 573 ms 98428 KB
63.txt AC 564 ms 98804 KB
64.txt AC 567 ms 102136 KB
65.txt AC 311 ms 64604 KB
66.txt AC 558 ms 102136 KB
67.txt AC 549 ms 101104 KB
68.txt AC 565 ms 100416 KB
69.txt AC 556 ms 102132 KB
70.txt AC 551 ms 100984 KB
71.txt AC 555 ms 102304 KB
72.txt AC 551 ms 99824 KB
73.txt AC 542 ms 100156 KB
74.txt AC 546 ms 99440 KB
75.txt AC 560 ms 101492 KB
76.txt AC 536 ms 99432 KB
77.txt AC 577 ms 99120 KB
78.txt AC 556 ms 99656 KB
79.txt AC 539 ms 95428 KB
80.txt AC 530 ms 97144 KB
81.txt AC 552 ms 101104 KB
82.txt AC 551 ms 100064 KB
83.txt AC 513 ms 101084 KB
84.txt AC 551 ms 98404 KB
85.txt AC 564 ms 100196 KB
86.txt AC 306 ms 62792 KB
87.txt AC 539 ms 99904 KB
88.txt AC 557 ms 102052 KB
89.txt AC 541 ms 100188 KB
90.txt AC 555 ms 101732 KB
91.txt AC 557 ms 99292 KB
92.txt AC 540 ms 103136 KB
93.txt AC 71 ms 20948 KB
94.txt AC 70 ms 23508 KB
95.txt AC 71 ms 19412 KB
96.txt AC 72 ms 22484 KB
97.txt AC 70 ms 18004 KB
98.txt AC 70 ms 20820 KB
99.txt AC 72 ms 21332 KB
s1.txt AC 71 ms 17876 KB
s2.txt AC 80 ms 21460 KB
s3.txt AC 88 ms 21204 KB