Submission #58234


Source Code Expand

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int N;
	static int[] a, b;
	static long sum;

	public static void main(String[] args) {
		N = sc.nextInt();
		a = new int[N];
		b = new int[N];
		long max = 0;
		for (int i = 0; i < N; ++i) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			sum += a[i];
		}
		for (int i = 0; i < N; ++i) {
			max = Math.max(max, (sum * (b[i] + 1) + sum - 1) / a[i]);
		}
		for (long i = max;; --i) {
			if (!possible(i)) {
				System.out.println(i + 1);
				return;
			}
		}
	}

	static boolean possible(long m) {
		long[] count = new long[N];
		long all = 0;
		St[] rem = new St[N];
		boolean ok = true;
		for (int i = 0; i < N; ++i) {
			count[i] = a[i] * m / sum;
			all += count[i];
			rem[i] = new St(a[i] * m - count[i] * sum, i);
			if (count[i] < b[i]) ok = false;
		}
		if (ok) return true;
		Arrays.sort(rem);
		for (int i = 0; i < Math.min(m - all, N); ++i) {
			++count[rem[i].i];
		}
		//		System.out.println(m + " " + Arrays.toString(count) + " " + all);
		for (int i = 0; i < N; ++i) {
			if (count[i] < b[i]) return false;
		}
		return true;
	}

	static class St implements Comparable<St> {
		long c;
		int i;

		St(long c, int i) {
			this.c = c;
			this.i = i;
		}

		public int compareTo(St o) {
			if (this.c == o.c) return this.i - o.i;
			if (this.c > o.c) return -1;
			return 1;
		}
	}

}

Submission Info

Submission Time
Task E - 選挙
User tomerun
Language Java (OpenJDK 1.7.0)
Score 0
Code Size 1496 Byte
Status WA
Exec Time 2124 ms
Memory 63584 KB

Judge Result

Set Name Bubunten All
Score / Max Score 0 / 50 0 / 150
Status
AC × 10
WA × 19
AC × 9
WA × 76
TLE × 7
Set Name Test Cases
Bubunten small01.txt, small02.txt, small03.txt, small04.txt, small05.txt, small06.txt, small07.txt, small08.txt, small09.txt, small10.txt, small11.txt, small12.txt, small13.txt, small14.txt, small15.txt, small16.txt, small17.txt, small18.txt, small19.txt, small20.txt, small21.txt, small22.txt, small23.txt, small24.txt, small25.txt, sample1.txt, sample2.txt, sample3.txt, 20_minimal.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, 20_minimal.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, dekai1.txt, dekai2.txt, small01.txt, small02.txt, small03.txt, small04.txt, small05.txt, small06.txt, small07.txt, small08.txt, small09.txt, small10.txt, small11.txt, small12.txt, small13.txt, small14.txt, small15.txt, small16.txt, small17.txt, small18.txt, small19.txt, small20.txt, small21.txt, small22.txt, small23.txt, small24.txt, small25.txt, yabame1.txt, yabame2.txt, yabame3.txt, yabame4.txt
Case Name Status Exec Time Memory
01.txt WA 1508 ms 61468 KB
02.txt WA 1646 ms 61648 KB
03.txt WA 926 ms 49464 KB
04.txt WA 778 ms 42648 KB
05.txt WA 1596 ms 62936 KB
06.txt WA 1345 ms 60384 KB
07.txt WA 739 ms 42820 KB
08.txt WA 1956 ms 59000 KB
09.txt WA 1952 ms 61728 KB
10.txt WA 1016 ms 52448 KB
11.txt WA 819 ms 47140 KB
12.txt WA 658 ms 39716 KB
13.txt WA 1004 ms 53208 KB
14.txt WA 729 ms 42828 KB
15.txt WA 993 ms 52984 KB
16.txt WA 541 ms 32372 KB
17.txt WA 1579 ms 61728 KB
18.txt WA 1300 ms 58764 KB
19.txt WA 893 ms 45832 KB
20.txt WA 720 ms 41484 KB
20_minimal.txt AC 446 ms 20256 KB
21.txt WA 872 ms 46380 KB
22.txt WA 1629 ms 63444 KB
23.txt WA 1642 ms 63372 KB
24.txt WA 865 ms 46016 KB
25.txt WA 599 ms 39692 KB
26.txt WA 764 ms 42660 KB
27.txt WA 759 ms 42500 KB
28.txt WA 698 ms 40396 KB
29.txt WA 926 ms 48956 KB
30.txt WA 698 ms 40332 KB
31.txt WA 769 ms 42120 KB
32.txt WA 705 ms 41704 KB
33.txt WA 599 ms 37880 KB
34.txt WA 649 ms 40640 KB
35.txt WA 774 ms 42640 KB
36.txt WA 797 ms 44024 KB
37.txt WA 886 ms 48308 KB
38.txt WA 808 ms 42688 KB
39.txt WA 790 ms 42724 KB
40.txt WA 867 ms 47148 KB
41.txt WA 883 ms 48480 KB
42.txt WA 537 ms 21424 KB
43.txt WA 448 ms 20260 KB
44.txt WA 614 ms 39316 KB
45.txt WA 600 ms 37260 KB
46.txt AC 517 ms 22196 KB
47.txt WA 617 ms 37676 KB
48.txt AC 528 ms 20272 KB
49.txt WA 1064 ms 53032 KB
50.txt WA 610 ms 38116 KB
51.txt WA 1986 ms 63452 KB
52.txt TLE 2007 ms 63300 KB
53.txt WA 1962 ms 63584 KB
54.txt WA 1988 ms 63516 KB
55.txt WA 1967 ms 60928 KB
56.txt WA 1947 ms 62072 KB
57.txt TLE 2037 ms 62388 KB
58.txt TLE 2040 ms 61776 KB
59.txt WA 1979 ms 62400 KB
60.txt WA 1985 ms 62096 KB
dekai1.txt WA 1363 ms 41052 KB
dekai2.txt WA 1311 ms 38480 KB
sample1.txt AC 454 ms 20272 KB
sample2.txt AC 460 ms 20276 KB
sample3.txt AC 465 ms 20276 KB
small01.txt WA 528 ms 26980 KB
small02.txt WA 490 ms 21100 KB
small03.txt WA 504 ms 22696 KB
small04.txt WA 480 ms 20912 KB
small05.txt AC 488 ms 20272 KB
small06.txt WA 540 ms 24360 KB
small07.txt AC 468 ms 20276 KB
small08.txt WA 556 ms 32364 KB
small09.txt WA 506 ms 21732 KB
small10.txt AC 519 ms 25764 KB
small11.txt WA 513 ms 24108 KB
small12.txt WA 499 ms 16820 KB
small13.txt WA 525 ms 30320 KB
small14.txt AC 430 ms 18140 KB
small15.txt WA 579 ms 37056 KB
small16.txt WA 461 ms 20168 KB
small17.txt AC 462 ms 17884 KB
small18.txt AC 466 ms 18660 KB
small19.txt WA 467 ms 18144 KB
small20.txt WA 481 ms 21724 KB
small21.txt WA 461 ms 19672 KB
small22.txt WA 468 ms 23264 KB
small23.txt WA 460 ms 21340 KB
small24.txt WA 425 ms 18140 KB
small25.txt WA 480 ms 24032 KB
yabame1.txt TLE 2084 ms 59668 KB
yabame2.txt TLE 2124 ms 59516 KB
yabame3.txt TLE 2039 ms 59776 KB
yabame4.txt TLE 2089 ms 59012 KB