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 AC
Exec Time 1411 ms
Memory 91920 KB

Judge Result

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