Time Lapse :3min 5sec

2961.java

java

import java.io.*;
import java.util.*;

public class Main {
    static int[][] dp;
    static int ans = 987654321, n;
    static Reader r = new Reader();
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception {
        dp = new int[1<<(n = r.nextInt())][2];
        for(int i = 0; i < n; ++i)
            ans = Math.min(Math.abs((dp[1<<i][0] = r.nextInt()) - (dp[1<<i][1] = r.nextInt())), ans);

        for(int i = 0; i < n; ++i)
            combination(1 << i, i);

        bw.write(Integer.toString(ans));
        bw.flush();
    }
    static void combination(int cmb, int val) {
        for(int i = val + 1; i < n; ++i) {
            ans = Math.min(Math.abs((dp[cmb | (1<<i)][0] = dp[cmb][0] * dp[1<<i][0]) - (dp[cmb | (1<<i)][1] = dp[cmb][1] + dp[1<<i][1])), ans);
            combination(cmb | (1<<i), i);
        }
    }

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            do {
                ret = (ret << 3) + (ret << 1) + (c & 0b1111);
            } while ((c = read()) >= '0' && c <= '9');

            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
    }
}