Submission #402426
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 count = 0; for (int i = 0; i < N; i++) { count += bucket[i]; if (count > i + 1) 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 | 2094 Byte |
Status | AC |
Exec Time | 504 ms |
Memory | 29004 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 | 124 ms | 8440 KB |
subtask0-sample02.txt | AC | 121 ms | 8476 KB |
subtask1-01.txt | AC | 121 ms | 8476 KB |
subtask1-02.txt | AC | 123 ms | 8400 KB |
subtask1-03.txt | AC | 122 ms | 8424 KB |
subtask1-04.txt | AC | 121 ms | 8472 KB |
subtask1-05.txt | AC | 122 ms | 8456 KB |
subtask1-06.txt | AC | 122 ms | 8488 KB |
subtask1-07.txt | AC | 124 ms | 8472 KB |
subtask1-08.txt | AC | 121 ms | 8444 KB |
subtask1-09.txt | AC | 121 ms | 8420 KB |
subtask1-10.txt | AC | 123 ms | 8488 KB |
subtask1-11.txt | AC | 123 ms | 8476 KB |
subtask1-12.txt | AC | 123 ms | 8476 KB |
subtask1-13.txt | AC | 121 ms | 8464 KB |
subtask1-14.txt | AC | 121 ms | 8476 KB |
subtask1-15.txt | AC | 141 ms | 8480 KB |
subtask2-01.txt | AC | 127 ms | 8620 KB |
subtask2-02.txt | AC | 130 ms | 9244 KB |
subtask2-03.txt | AC | 134 ms | 10044 KB |
subtask2-04.txt | AC | 203 ms | 17424 KB |
subtask2-05.txt | AC | 309 ms | 24656 KB |
subtask2-06.txt | AC | 394 ms | 28848 KB |
subtask2-07.txt | AC | 457 ms | 28656 KB |
subtask2-08.txt | AC | 490 ms | 28860 KB |
subtask2-09.txt | AC | 491 ms | 28908 KB |
subtask2-10.txt | AC | 448 ms | 28944 KB |
subtask2-11.txt | AC | 494 ms | 28912 KB |
subtask2-12.txt | AC | 491 ms | 28912 KB |
subtask2-13.txt | AC | 463 ms | 28944 KB |
subtask2-14.txt | AC | 495 ms | 29004 KB |
subtask2-15.txt | AC | 504 ms | 28892 KB |