Submission #1964142


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[][][] 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]));
					}
				}
			}
		}
		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)
					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

Submission Time
Task F - Intervals
User fortoobye
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 1710 Byte
Status WA
Exec Time 2112 ms
Memory 528012 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 2
AC × 7
WA × 1
TLE × 37
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt TLE 2111 ms 499876 KB
001.txt AC 1507 ms 211308 KB
002.txt TLE 2111 ms 521460 KB
003.txt TLE 2111 ms 492176 KB
004.txt TLE 2111 ms 524800 KB
005.txt TLE 2110 ms 486780 KB
006.txt TLE 2111 ms 528012 KB
007.txt TLE 2111 ms 496840 KB
008.txt TLE 2111 ms 514900 KB
009.txt AC 722 ms 126484 KB
010.txt TLE 2111 ms 512352 KB
011.txt TLE 2111 ms 494948 KB
012.txt TLE 2111 ms 517200 KB
013.txt AC 693 ms 126372 KB
014.txt TLE 2111 ms 513452 KB
015.txt WA 1477 ms 210304 KB
016.txt TLE 2111 ms 527988 KB
017.txt TLE 2111 ms 499228 KB
018.txt TLE 2111 ms 519800 KB
019.txt TLE 2111 ms 499788 KB
020.txt AC 96 ms 21716 KB
021.txt AC 95 ms 19412 KB
022.txt TLE 2111 ms 512844 KB
023.txt TLE 2111 ms 524456 KB
024.txt TLE 2111 ms 513472 KB
025.txt TLE 2111 ms 500868 KB
026.txt TLE 2112 ms 526168 KB
027.txt TLE 2111 ms 516776 KB
028.txt TLE 2111 ms 518132 KB
029.txt TLE 2111 ms 508036 KB
030.txt TLE 2111 ms 515968 KB
031.txt TLE 2111 ms 498852 KB
032.txt TLE 2111 ms 499776 KB
033.txt TLE 2111 ms 525056 KB
034.txt TLE 2111 ms 519100 KB
035.txt TLE 2111 ms 522112 KB
036.txt TLE 2111 ms 495888 KB
037.txt TLE 2111 ms 526484 KB
038.txt TLE 2111 ms 520544 KB
039.txt TLE 2111 ms 510368 KB
040.txt TLE 2111 ms 516584 KB
041.txt TLE 2111 ms 518636 KB
042.txt TLE 2111 ms 495936 KB
example0.txt AC 96 ms 20820 KB
example1.txt AC 99 ms 21076 KB