Submission #402436
Source Code Expand
using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.IO; class Myon { public Myon() { } public static int Main() { new Myon().calc(); return 0; } Scanner cin; void calc() { cin = new Scanner(); int N = cin.nextInt(); int[] H = new int[N]; int[] S = new int[N]; for (int i = 0; i < N; i++) { H[i] = cin.nextInt(); S[i] = cin.nextInt(); } long left = 0; //達成不可能な最大数 long right = (long)1e18; //達成可能な最小数 while (right - left > 1) { long mid = (left + right) / 2; if (check(H, S, mid)) right = mid; else left = mid; } Console.WriteLine(right); } bool check(int[] H, int[] S, long mid) { int N = H.Length; int[] bucket = new int[N + 1]; for (int i = 0; i < N; i++) { if (H[i] > mid) return false; int sec = (int)Math.Min(N, (mid - H[i]) / S[i]); bucket[sec]++; } int[] array = new int[N]; int cnt = 0; for (int i = 0; i <= N; i++) { for (int j = 0; j < bucket[i]; j++) { array[cnt++] = i; } } for (int i = 0; i < N; i++) { if (array[i] < i) return false; } return true; } } class Scanner { string[] s; int i; char[] cs = new char[] { ' ' }; public Scanner() { s = new string[0]; i = 0; } public string next() { if (i < s.Length) return s[i++]; string st = Console.ReadLine(); while (st == "") st = Console.ReadLine(); s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries); i = 0; return s[i++]; } public int nextInt() { return int.Parse(next()); } public long nextLong() { return long.Parse(next()); } public double nextDouble() { return double.Parse(next()); } }
Submission Info
Submission Time | |
---|---|
Task | D - 射撃王 |
User | chokudai |
Language | C# (Mono 3.2.1.0) |
Score | 100 |
Code Size | 2273 Byte |
Status | AC |
Exec Time | 582 ms |
Memory | 30896 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 70 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0-sample01.txt, subtask0-sample02.txt |
Subtask1 | subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt |
Subtask2 | subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0-sample01.txt | AC | 103 ms | 8876 KB |
subtask0-sample02.txt | AC | 103 ms | 8876 KB |
subtask1-01.txt | AC | 102 ms | 8872 KB |
subtask1-02.txt | AC | 103 ms | 8876 KB |
subtask1-03.txt | AC | 103 ms | 8912 KB |
subtask1-04.txt | AC | 103 ms | 8824 KB |
subtask1-05.txt | AC | 102 ms | 8876 KB |
subtask1-06.txt | AC | 103 ms | 8876 KB |
subtask1-07.txt | AC | 102 ms | 8876 KB |
subtask1-08.txt | AC | 105 ms | 8872 KB |
subtask1-09.txt | AC | 106 ms | 8852 KB |
subtask1-10.txt | AC | 105 ms | 8876 KB |
subtask1-11.txt | AC | 104 ms | 8872 KB |
subtask1-12.txt | AC | 106 ms | 8860 KB |
subtask1-13.txt | AC | 102 ms | 8880 KB |
subtask1-14.txt | AC | 107 ms | 8908 KB |
subtask1-15.txt | AC | 112 ms | 8872 KB |
subtask2-01.txt | AC | 110 ms | 9132 KB |
subtask2-02.txt | AC | 114 ms | 10028 KB |
subtask2-03.txt | AC | 121 ms | 11112 KB |
subtask2-04.txt | AC | 209 ms | 22560 KB |
subtask2-05.txt | AC | 342 ms | 29004 KB |
subtask2-06.txt | AC | 449 ms | 30804 KB |
subtask2-07.txt | AC | 528 ms | 30812 KB |
subtask2-08.txt | AC | 569 ms | 30892 KB |
subtask2-09.txt | AC | 582 ms | 30808 KB |
subtask2-10.txt | AC | 514 ms | 30896 KB |
subtask2-11.txt | AC | 542 ms | 30896 KB |
subtask2-12.txt | AC | 566 ms | 30880 KB |
subtask2-13.txt | AC | 535 ms | 30800 KB |
subtask2-14.txt | AC | 573 ms | 30892 KB |
subtask2-15.txt | AC | 572 ms | 30864 KB |