AtCoder Grand Contest 001

Submission #811871

Source codeソースコード

from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX*2+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2])%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup)*pow(2,p-2,p)+p) % p
solve()

Submission

Task問題 E - BBQ Hard
User nameユーザ名 Tawara
Created time投稿日時
Language言語 PyPy2 (5.6.0)
Status状態 AC
Score得点 1400
Source lengthソースコード長 907 Byte
File nameファイル名
Exec time実行時間 1998 ms
Memory usageメモリ使用量 189084 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample-01.txt
All 1400 / 1400 sample-01.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 657 ms 140956 KB
01-02.txt AC 1401 ms 141852 KB
01-03.txt AC 1701 ms 166556 KB
01-04.txt AC 1998 ms 188444 KB
01-05.txt AC 1943 ms 188316 KB
01-06.txt AC 1669 ms 143644 KB
01-07.txt AC 298 ms 139804 KB
01-08.txt AC 609 ms 143132 KB
01-09.txt AC 1009 ms 143644 KB
01-10.txt AC 1929 ms 189084 KB
01-11.txt AC 1997 ms 189084 KB
01-12.txt AC 1850 ms 166684 KB
01-13.txt AC 1963 ms 188188 KB
01-14.txt AC 1923 ms 188188 KB
sample-01.txt AC 305 ms 139804 KB