Submission #58961
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) { long start = System.currentTimeMillis(); 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]; } long ans = 1L << 60; for (int i = 0; i < N; ++i) { long mv = (long) Math.ceil(1.0 * (b[i] - 1) * sum / a[i]); for (long j = mv; j <= mv + a[i]; ++j) { if (possible(j)) { ans = Math.min(ans, j); break; } } } // long ans = max; // for (long i = max; i >= 0 && System.currentTimeMillis() - start < 1900; --i) { // if (possible(i)) { // ans = i; // } // } System.out.println(ans); } 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 | F - Uinny |
User | tomerun |
Language | Java (OpenJDK 1.7.0) |
Score | 0 |
Code Size | 1781 Byte |
Status | RE |
Exec Time | 981 ms |
Memory | 188400 KB |
Judge Result
Set Name | 010_01 | 010_02 | 010_03 | 010_04 | 010_05 | 010_06 | 010_07 | 010_08 | 010_09 | 010_10 | 010_11 | 010_12 | 010_13 | 010_14 | 010_15 | 010_16 | 010_17 | 010_18 | 010_19 | 010_20 | 010_21 | 010_22 | 010_23 | 010_24 | 010_25 | 010_26 | 010_27 | 010_28 | 010_29 | 010_30 | 010_31 | 010_32 | 010_33 | 010_34 | 010_35 | 010_36 | 010_37 | 010_38 | 010_39 | 010_40 | 010_41 | 010_42 | 010_43 | 010_44 | 010_45 | 010_46 | 010_47 | 010_48 | 010_49 | 010_50 | 010_51 | 010_52 | 010_53 | 010_54 | 010_55 | 010_56 | 010_57 | 010_58 | 010_59 | 010_60 | 010_61 | 010_62 | 010_63 | 010_64 | 010_65 | 010_66 | 010_67 | 010_68 | 010_69 | 010_70 | 010_71 | 010_72 | 010_73 | 010_74 | 010_75 | 010_76 | 010_77 | 010_78 | 010_79 | 010_80 | 010_81 | 010_82 | 010_83 | 010_84 | 010_85 | 010_86 | 010_87 | 010_88 | 010_89 | 010_90 | 010_91 | 010_92 | 010_93 | 010_94 | 010_95 | 010_96 | 010_97 | 010_98 | 010_99 | sample | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | 0 / 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Status |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Set Name | Test Cases |
---|---|
010_01 | 010_01.txt |
010_02 | 010_02.txt |
010_03 | 010_03.txt |
010_04 | 010_04.txt |
010_05 | 010_05.txt |
010_06 | 010_06.txt |
010_07 | 010_07.txt |
010_08 | 010_08.txt |
010_09 | 010_09.txt |
010_10 | 010_10.txt |
010_11 | 010_11.txt |
010_12 | 010_12.txt |
010_13 | 010_13.txt |
010_14 | 010_14.txt |
010_15 | 010_15.txt |
010_16 | 010_16.txt |
010_17 | 010_17.txt |
010_18 | 010_18.txt |
010_19 | 010_19.txt |
010_20 | 010_20.txt |
010_21 | 010_21.txt |
010_22 | 010_22.txt |
010_23 | 010_23.txt |
010_24 | 010_24.txt |
010_25 | 010_25.txt |
010_26 | 010_26.txt |
010_27 | 010_27.txt |
010_28 | 010_28.txt |
010_29 | 010_29.txt |
010_30 | 010_30.txt |
010_31 | 010_31.txt |
010_32 | 010_32.txt |
010_33 | 010_33.txt |
010_34 | 010_34.txt |
010_35 | 010_35.txt |
010_36 | 010_36.txt |
010_37 | 010_37.txt |
010_38 | 010_38.txt |
010_39 | 010_39.txt |
010_40 | 010_40.txt |
010_41 | 010_41.txt |
010_42 | 010_42.txt |
010_43 | 010_43.txt |
010_44 | 010_44.txt |
010_45 | 010_45.txt |
010_46 | 010_46.txt |
010_47 | 010_47.txt |
010_48 | 010_48.txt |
010_49 | 010_49.txt |
010_50 | 010_50.txt |
010_51 | 010_51.txt |
010_52 | 010_52.txt |
010_53 | 010_53.txt |
010_54 | 010_54.txt |
010_55 | 010_55.txt |
010_56 | 010_56.txt |
010_57 | 010_57.txt |
010_58 | 010_58.txt |
010_59 | 010_59.txt |
010_60 | 010_60.txt |
010_61 | 010_61.txt |
010_62 | 010_62.txt |
010_63 | 010_63.txt |
010_64 | 010_64.txt |
010_65 | 010_65.txt |
010_66 | 010_66.txt |
010_67 | 010_67.txt |
010_68 | 010_68.txt |
010_69 | 010_69.txt |
010_70 | 010_70.txt |
010_71 | 010_71.txt |
010_72 | 010_72.txt |
010_73 | 010_73.txt |
010_74 | 010_74.txt |
010_75 | 010_75.txt |
010_76 | 010_76.txt |
010_77 | 010_77.txt |
010_78 | 010_78.txt |
010_79 | 010_79.txt |
010_80 | 010_80.txt |
010_81 | 010_81.txt |
010_82 | 010_82.txt |
010_83 | 010_83.txt |
010_84 | 010_84.txt |
010_85 | 010_85.txt |
010_86 | 010_86.txt |
010_87 | 010_87.txt |
010_88 | 010_88.txt |
010_89 | 010_89.txt |
010_90 | 010_90.txt |
010_91 | 010_91.txt |
010_92 | 010_92.txt |
010_93 | 010_93.txt |
010_94 | 010_94.txt |
010_95 | 010_95.txt |
010_96 | 010_96.txt |
010_97 | 010_97.txt |
010_98 | 010_98.txt |
010_99 | 010_99.txt |
sample | sample.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
010_01.txt | RE | 573 ms | 21040 KB |
010_02.txt | RE | 550 ms | 21168 KB |
010_03.txt | RE | 588 ms | 21160 KB |
010_04.txt | RE | 705 ms | 142372 KB |
010_05.txt | RE | 567 ms | 21216 KB |
010_06.txt | RE | 506 ms | 21172 KB |
010_07.txt | RE | 651 ms | 21172 KB |
010_08.txt | RE | 553 ms | 21196 KB |
010_09.txt | RE | 557 ms | 21152 KB |
010_10.txt | RE | 713 ms | 21168 KB |
010_11.txt | RE | 583 ms | 21124 KB |
010_12.txt | RE | 689 ms | 21172 KB |
010_13.txt | RE | 549 ms | 21212 KB |
010_14.txt | RE | 744 ms | 145324 KB |
010_15.txt | RE | 479 ms | 21044 KB |
010_16.txt | RE | 590 ms | 21164 KB |
010_17.txt | RE | 544 ms | 21164 KB |
010_18.txt | RE | 683 ms | 21092 KB |
010_19.txt | RE | 595 ms | 21156 KB |
010_20.txt | RE | 608 ms | 21228 KB |
010_21.txt | RE | 644 ms | 21220 KB |
010_22.txt | RE | 735 ms | 154660 KB |
010_23.txt | RE | 560 ms | 21292 KB |
010_24.txt | RE | 564 ms | 21144 KB |
010_25.txt | RE | 745 ms | 104372 KB |
010_26.txt | RE | 644 ms | 21172 KB |
010_27.txt | RE | 676 ms | 21168 KB |
010_28.txt | RE | 552 ms | 21172 KB |
010_29.txt | RE | 529 ms | 21160 KB |
010_30.txt | RE | 572 ms | 21172 KB |
010_31.txt | RE | 543 ms | 21096 KB |
010_32.txt | RE | 493 ms | 36540 KB |
010_33.txt | RE | 741 ms | 132668 KB |
010_34.txt | RE | 564 ms | 21168 KB |
010_35.txt | RE | 596 ms | 21172 KB |
010_36.txt | RE | 497 ms | 21160 KB |
010_37.txt | RE | 582 ms | 21220 KB |
010_38.txt | RE | 502 ms | 21220 KB |
010_39.txt | RE | 497 ms | 21160 KB |
010_40.txt | RE | 758 ms | 21172 KB |
010_41.txt | RE | 640 ms | 21164 KB |
010_42.txt | RE | 546 ms | 21156 KB |
010_43.txt | RE | 705 ms | 21112 KB |
010_44.txt | RE | 779 ms | 21236 KB |
010_45.txt | RE | 673 ms | 21100 KB |
010_46.txt | RE | 804 ms | 142640 KB |
010_47.txt | RE | 620 ms | 21168 KB |
010_48.txt | RE | 825 ms | 148024 KB |
010_49.txt | RE | 518 ms | 21156 KB |
010_50.txt | RE | 782 ms | 21180 KB |
010_51.txt | RE | 683 ms | 21172 KB |
010_52.txt | RE | 604 ms | 21096 KB |
010_53.txt | RE | 871 ms | 124460 KB |
010_54.txt | RE | 724 ms | 21168 KB |
010_55.txt | RE | 530 ms | 21224 KB |
010_56.txt | RE | 641 ms | 21152 KB |
010_57.txt | RE | 546 ms | 21224 KB |
010_58.txt | RE | 596 ms | 21168 KB |
010_59.txt | RE | 650 ms | 21044 KB |
010_60.txt | RE | 566 ms | 21156 KB |
010_61.txt | RE | 589 ms | 21156 KB |
010_62.txt | RE | 553 ms | 21168 KB |
010_63.txt | RE | 510 ms | 21152 KB |
010_64.txt | RE | 981 ms | 156720 KB |
010_65.txt | RE | 648 ms | 21160 KB |
010_66.txt | RE | 691 ms | 21084 KB |
010_67.txt | RE | 788 ms | 21216 KB |
010_68.txt | RE | 731 ms | 117588 KB |
010_69.txt | RE | 704 ms | 21164 KB |
010_70.txt | RE | 553 ms | 21088 KB |
010_71.txt | RE | 786 ms | 94644 KB |
010_72.txt | RE | 584 ms | 21172 KB |
010_73.txt | RE | 777 ms | 105012 KB |
010_74.txt | RE | 965 ms | 178860 KB |
010_75.txt | RE | 501 ms | 21168 KB |
010_76.txt | RE | 811 ms | 143792 KB |
010_77.txt | RE | 796 ms | 138392 KB |
010_78.txt | RE | 558 ms | 21156 KB |
010_79.txt | RE | 622 ms | 21156 KB |
010_80.txt | RE | 620 ms | 21168 KB |
010_81.txt | RE | 636 ms | 21224 KB |
010_82.txt | RE | 607 ms | 21144 KB |
010_83.txt | RE | 660 ms | 60980 KB |
010_84.txt | RE | 558 ms | 21036 KB |
010_85.txt | RE | 734 ms | 21172 KB |
010_86.txt | RE | 973 ms | 187628 KB |
010_87.txt | RE | 586 ms | 21172 KB |
010_88.txt | RE | 756 ms | 21168 KB |
010_89.txt | RE | 884 ms | 188400 KB |
010_90.txt | RE | 662 ms | 21176 KB |
010_91.txt | RE | 602 ms | 21220 KB |
010_92.txt | RE | 602 ms | 21164 KB |
010_93.txt | RE | 585 ms | 21144 KB |
010_94.txt | RE | 765 ms | 21196 KB |
010_95.txt | RE | 716 ms | 43324 KB |
010_96.txt | RE | 561 ms | 21220 KB |
010_97.txt | RE | 643 ms | 95396 KB |
010_98.txt | RE | 523 ms | 21036 KB |
010_99.txt | RE | 801 ms | 177448 KB |
sample.txt | RE | 502 ms | 20140 KB |