Submission #409111


Source Code Expand

n = input()
hl = []
sl = []
for i in xrange(n):
    h, s = map(int, raw_input().split())
    hl.append(h)
    sl.append(s)
left = 0; right = 10**14
while True:
    mid = (left + right) / 2
    ok = True
    tl = []
    for i in xrange(n):
        if mid < hl[i]:
            ok = False
            break
        tl.append((mid - hl[i]) / sl[i])
    tl.sort()
    cnt = 0
    if ok:
        for i in xrange(n):
            while cnt < n and tl[cnt] <= i:
                cnt += 1
            if cnt > i+1:
                ok = False
                break
    if not ok:
        if left==mid:
            break
        left = mid
    else:
        right = mid
print left+1

Submission Info

Submission Time
Task D - 射撃王
User yaketake08
Language Python (2.7.3)
Score 30
Code Size 704 Byte
Status TLE
Exec Time 5037 ms
Memory 13404 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 0 / 70
Status
AC × 2
AC × 17
AC × 22
TLE × 10
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 54 ms 3368 KB
subtask0-sample02.txt AC 57 ms 3308 KB
subtask1-01.txt AC 53 ms 3368 KB
subtask1-02.txt AC 53 ms 3308 KB
subtask1-03.txt AC 56 ms 3372 KB
subtask1-04.txt AC 56 ms 3368 KB
subtask1-05.txt AC 54 ms 3372 KB
subtask1-06.txt AC 63 ms 3316 KB
subtask1-07.txt AC 56 ms 3372 KB
subtask1-08.txt AC 59 ms 3372 KB
subtask1-09.txt AC 57 ms 3268 KB
subtask1-10.txt AC 57 ms 3268 KB
subtask1-11.txt AC 59 ms 3324 KB
subtask1-12.txt AC 57 ms 3376 KB
subtask1-13.txt AC 57 ms 3368 KB
subtask1-14.txt AC 58 ms 3360 KB
subtask1-15.txt AC 56 ms 3372 KB
subtask2-01.txt AC 75 ms 3368 KB
subtask2-02.txt AC 161 ms 3496 KB
subtask2-03.txt AC 216 ms 3636 KB
subtask2-04.txt AC 1678 ms 5368 KB
subtask2-05.txt AC 4183 ms 8364 KB
subtask2-06.txt TLE 5035 ms 11392 KB
subtask2-07.txt TLE 5035 ms 12356 KB
subtask2-08.txt TLE 5035 ms 13404 KB
subtask2-09.txt TLE 5035 ms 13304 KB
subtask2-10.txt TLE 5035 ms 10888 KB
subtask2-11.txt TLE 5034 ms 13200 KB
subtask2-12.txt TLE 5037 ms 13396 KB
subtask2-13.txt TLE 5034 ms 13288 KB
subtask2-14.txt TLE 5033 ms 13384 KB
subtask2-15.txt TLE 5034 ms 13384 KB