結果

問題 No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ
ユーザー titia
提出日時 2023-12-09 02:02:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,751 ms / 3,000 ms
コード長 1,047 bytes
コンパイル時間 636 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 80,472 KB
最終ジャッジ日時 2024-09-27 03:26:37
合計ジャッジ時間 24,963 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
input = sys.stdin.readline
from collections import Counter
from bisect import bisect

M=int(input())
G=list(map(int,input().split()))
H=list(map(int,input().split()))

DP1=[(0,0)]

for i in range(14):
    NDP1=[]
    for x,y in DP1:
        NDP1.append((x+1,(y+G[i])%M))
        NDP1.append((x,(y+H[i])%M))

    DP1=NDP1

DP2=[(0,0)]

for i in range(14,28):
    NDP2=[]
    for x,y in DP2:
        NDP2.append((x+1,(y+G[i])%M))
        NDP2.append((x,(y+H[i])%M))

    DP2=NDP2

LIST1=[[] for i in range(29)]

for x,y in DP1:
    LIST1[x].append(y)

for i in range(29):
    LIST1[i]=Counter(LIST1[i])

LIST2=[[] for i in range(29)]

for x,y in DP2:
    LIST2[x].append(y)

for i in range(29):
    LIST2[i].sort()

Q=int(input())
for tests in range(Q):
    K,X=map(int,input().split())

    ANS=0

    for i in range(K+1):
        for c in LIST1[i]:
            ANS+=LIST1[i][c]*(bisect(LIST2[K-i],M-c-1)-bisect(LIST2[K-i],X-c-1))
            ANS+=LIST1[i][c]*(bisect(LIST2[K-i],2*M-c-1)-bisect(LIST2[K-i],M+X-c-1))

    print(ANS)
    
0