Submission #10687383


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import cmp_to_key
import itertools

N, T = map(int, readline().split())
m = map(int, read().split())
AB0 = []
AB1 = []
for a,b in zip(m,m):
    if a == 0:
        AB0.append(b)
    else:
        AB1.append((a,b))

def sort_func(ab0, ab1):
    a0, b0 = ab0
    a1, b1 = ab1
    return a1*(1+b0) - a0*(1+b1)

AB0.sort()
AB1.sort(key=cmp_to_key(sort_func))
AB0, AB1

def compute_0():
    INF = T + 1
    dp = [INF] * 40
    dp[0] = 0
    for a,b in AB1:
        for n in range(39, -1, -1):
            if dp[n] > T:
                continue
            x = (dp[n] + 1) * (a + 1) + b
            if x < dp[n+1]:
                dp[n+1] = x
    return dp

def compute_1():
    return [0] + list(itertools.accumulate(x + 1 for x in AB0))

dp0 = compute_0()
dp1 = compute_1()

R = len(dp1) - 1
answer = 0
for i,x in enumerate(dp0):
    if x > T:
        break
    while x + dp1[R] > T:
        R -= 1
    value = i + R
    if answer < value:
        answer = value

print(answer)

Submission Info

Submission Time
Task D - Manga Market
User maspy
Language PyPy3 (2.4.0)
Score 800
Code Size 1161 Byte
Status
Exec Time 1411 ms
Memory 91920 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00-sample-00, 00-sample-01, 00-sample-02, 00-sample-03
All 800 / 800 00-sample-00, 00-sample-01, 00-sample-02, 00-sample-03, 01-handmade-00, 01-handmade-01, 01-handmade-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 02-small-00, 02-small-01, 02-small-02, 02-small-03, 02-small-04, 02-small-05, 02-small-06, 02-small-07, 02-small-08, 02-small-09, 02-small-10, 02-small-11, 02-small-12, 02-small-13, 02-small-14, 02-small-15, 02-small-16, 02-small-17, 02-small-18, 02-small-19, 03-large-00, 03-large-01, 03-large-02, 03-large-03, 03-large-04, 03-large-05, 03-large-06, 03-large-07, 03-large-08, 03-large-09, 03-large-10, 03-large-11, 03-large-12, 03-large-13, 03-large-14, 04-large2-00, 04-large2-01, 04-large2-02, 04-large2-03, 04-large2-04, 04-large2-05, 04-large2-06, 04-large2-07, 04-large2-08, 04-large2-09, 04-large2-10, 04-large2-11, 04-large2-12, 04-large2-13, 04-large2-14, 05-a01-00, 05-a01-01, 05-a01-02, 05-a01-03, 05-a01-04, 05-a01-05, 05-a01-06, 06-almost_a0-00, 06-almost_a0-01, 06-almost_a0-02, 06-almost_a0-03, 06-almost_a0-04, 06-almost_a0-05, 06-almost_a0-06, 07-a01_almost_a0-00, 07-a01_almost_a0-01, 07-a01_almost_a0-02, 07-a01_almost_a0-03, 07-a01_almost_a0-04, 07-a01_almost_a0-05, 07-a01_almost_a0-06
Case Name Status Exec Time Memory
00-sample-00 168 ms 38384 KB
00-sample-01 166 ms 38256 KB
00-sample-02 166 ms 38256 KB
00-sample-03 168 ms 38256 KB
01-handmade-00 167 ms 38256 KB
01-handmade-01 273 ms 80012 KB
01-handmade-02 1256 ms 90604 KB
01-handmade-03 456 ms 91920 KB
01-handmade-04 931 ms 87564 KB
01-handmade-05 456 ms 85480 KB
02-small-00 174 ms 38256 KB
02-small-01 174 ms 38256 KB
02-small-02 180 ms 38384 KB
02-small-03 170 ms 38256 KB
02-small-04 169 ms 38256 KB
02-small-05 171 ms 38256 KB
02-small-06 170 ms 38256 KB
02-small-07 168 ms 38256 KB
02-small-08 171 ms 38256 KB
02-small-09 169 ms 38256 KB
02-small-10 170 ms 38256 KB
02-small-11 174 ms 38460 KB
02-small-12 170 ms 38256 KB
02-small-13 169 ms 38256 KB
02-small-14 165 ms 38384 KB
02-small-15 166 ms 38256 KB
02-small-16 169 ms 38384 KB
02-small-17 169 ms 38256 KB
02-small-18 168 ms 38256 KB
02-small-19 168 ms 38256 KB
03-large-00 529 ms 54244 KB
03-large-01 657 ms 60460 KB
03-large-02 196 ms 40688 KB
03-large-03 1411 ms 89040 KB
03-large-04 324 ms 46192 KB
03-large-05 1298 ms 82548 KB
03-large-06 713 ms 60812 KB
03-large-07 1362 ms 89204 KB
03-large-08 1029 ms 74156 KB
03-large-09 1046 ms 73816 KB
03-large-10 429 ms 49304 KB
03-large-11 463 ms 52496 KB
03-large-12 469 ms 51940 KB
03-large-13 655 ms 60344 KB
03-large-14 475 ms 52412 KB
04-large2-00 464 ms 54012 KB
04-large2-01 917 ms 74816 KB
04-large2-02 857 ms 71004 KB
04-large2-03 963 ms 77128 KB
04-large2-04 404 ms 50356 KB
04-large2-05 197 ms 40816 KB
04-large2-06 802 ms 70492 KB
04-large2-07 329 ms 46384 KB
04-large2-08 215 ms 41584 KB
04-large2-09 399 ms 50300 KB
04-large2-10 577 ms 59872 KB
04-large2-11 249 ms 42864 KB
04-large2-12 667 ms 63004 KB
04-large2-13 1132 ms 88100 KB
04-large2-14 620 ms 60916 KB
05-a01-00 322 ms 52208 KB
05-a01-01 400 ms 58656 KB
05-a01-02 203 ms 41200 KB
05-a01-03 711 ms 83104 KB
05-a01-04 257 ms 45424 KB
05-a01-05 639 ms 79252 KB
05-a01-06 427 ms 59116 KB
06-almost_a0-00 223 ms 52080 KB
06-almost_a0-01 275 ms 74024 KB
06-almost_a0-02 270 ms 70736 KB
06-almost_a0-03 285 ms 75320 KB
06-almost_a0-04 216 ms 49264 KB
06-almost_a0-05 181 ms 39664 KB
06-almost_a0-06 274 ms 70936 KB
07-a01_almost_a0-00 232 ms 51824 KB
07-a01_almost_a0-01 244 ms 57968 KB
07-a01_almost_a0-02 182 ms 40048 KB
07-a01_almost_a0-03 297 ms 81468 KB
07-a01_almost_a0-04 209 ms 44656 KB
07-a01_almost_a0-05 281 ms 77860 KB
07-a01_almost_a0-06 246 ms 58352 KB