Submission #1964139

---

Source Code Expand

import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Main {

	public void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[][] a = new long[n][2];
		for (int i = 0; i < n; ++i) {
			a[i][0] = sc.nextLong();
			a[i][1] = sc.nextLong();
		}
		Arrays.sort(a, new Comparator<long[]>() {
			@Override
			public int compare(long[] arg0, long[] arg1) {
				return -Long.compare(arg0[0] + arg0[1], arg1[0] + arg1[1]);
			}
		});
		long ans = Long.MAX_VALUE / 3;
		long[][] f = new long[n + 1][n + 1];
		for (int i = 0; i < f.length; ++i)
			for (int j = 0; j < f[i].length; ++j)
				f[i][j] = Long.MAX_VALUE / 3;
		f[0][0] = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j <= i; ++j) {
				f[i - j][j + 1] = Math.min(f[i - j][j + 1], f[i - j][j] + a[i][0] + j * (a[i][0] + a[i][1]));
				f[i - j + 1][j] = Math.min(f[i - j + 1][j], f[i - j][j] + a[i][1] + (i - j) * (a[i][0] + a[i][1]));
			}
		}
		for (int i = 0; i <= n; ++i) {
			ans = Math.min(ans, f[i][n - i]);
		}

		if (n % 2 == 1) {
			long[][][] g = new long[n + 1][n + 1][2];
			for (int i = 0; i < g.length; ++i)
				for (int j = 0; j < g[i].length; ++j)
					for (int k = 0; k < g[i][j].length; ++k)
						g[i][j][k] = Long.MAX_VALUE / 3;
			g[0][0][0] = 0;
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j <= i; ++j) {
					for (int k = 0; k <= 1; ++k) {
						g[i - j][j + 1][k] = Math.min(g[i - j][j + 1][k],
								g[i - j][j][k] + a[i][0] + j * (a[i][0] + a[i][1]));
						g[i - j + 1][j][k] = Math.min(g[i - j + 1][j][k],
								g[i - j][j][k] + a[i][1] + (i - j) * (a[i][0] + a[i][1]));
						if (k == 0) {
							g[i - j][j][1] = Math.min(g[i - j][j][1], g[i - j][j][0] + (n - 1) * (a[i][0] + a[i][1]));
						}
						if (i + j + k == n)
							ans = Math.min(ans, g[i][j][k]);
					}
				}
			}
		}
		System.out.println(ans);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

	public static void main(String[] args) throws FileNotFoundException {
		new Main().run();
	}
}

Submission Info

Judge Result