#145542 (Python2) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	startcpp
提出日時	2017-01-25 11:57:27
言語	Python2 (2.7.18)
結果	TLE
実行時間	-
コード長	631 bytes
コンパイル時間	602 ms
コンパイル使用メモリ	7,076 KB
実行使用メモリ	27,564 KB
最終ジャッジ日時	2024-12-23 08:18:59
合計ジャッジ時間	118,518 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	13 ms 13,636 KB
testcase_01	AC	12 ms 20,776 KB
testcase_02	AC	12 ms 13,768 KB
testcase_03	AC	12 ms 13,644 KB
testcase_04	AC	11 ms 13,760 KB
testcase_05	AC	11 ms 20,900 KB
testcase_06	AC	11 ms 13,768 KB
testcase_07	AC	12 ms 6,820 KB
testcase_08	AC	11 ms 13,768 KB
testcase_09	AC	12 ms 18,632 KB
testcase_10	AC	11 ms 13,764 KB
testcase_11	AC	13 ms 13,764 KB
testcase_12	AC	12 ms 13,760 KB
testcase_13	AC	12 ms 17,556 KB
testcase_14	AC	11 ms 13,768 KB
testcase_15	AC	12 ms 21,540 KB
testcase_16	AC	12 ms 21,416 KB
testcase_17	AC	12 ms 13,764 KB
testcase_18	AC	12 ms 13,768 KB
testcase_19	AC	12 ms 21,088 KB
testcase_20	AC	16 ms 13,764 KB
testcase_21	AC	62 ms 20,964 KB
testcase_22	AC	65 ms 13,764 KB
testcase_23	AC	13 ms 18,400 KB
testcase_24	AC	13 ms 13,768 KB
testcase_25	AC	168 ms 13,984 KB
testcase_26	AC	100 ms 13,764 KB
testcase_27	AC	22 ms 25,056 KB
testcase_28	AC	21 ms 13,760 KB
testcase_29	AC	47 ms 21,492 KB
testcase_30	AC	47 ms 13,760 KB
testcase_31	AC	69 ms 23,580 KB
testcase_32	AC	122 ms 13,768 KB
testcase_33	AC	123 ms 13,860 KB
testcase_34	AC	122 ms 13,864 KB
testcase_35	AC	83 ms 13,772 KB
testcase_36	AC	81 ms 21,024 KB
testcase_37	AC	15 ms 13,764 KB
testcase_38	AC	15 ms 13,760 KB
testcase_39	AC	88 ms 20,356 KB
testcase_40	AC	74 ms 13,764 KB
testcase_41	AC	72 ms 13,764 KB
testcase_42	AC	74 ms 13,760 KB
testcase_43	AC	54 ms 27,308 KB
testcase_44	AC	53 ms 13,764 KB
testcase_45	AC	26 ms 6,816 KB
testcase_46	AC	27 ms 6,820 KB
testcase_47	AC	34 ms 6,820 KB
testcase_48	AC	191 ms 6,820 KB
testcase_49	AC	190 ms 6,912 KB
testcase_50	AC	65 ms 6,816 KB
testcase_51	AC	66 ms 6,816 KB
testcase_52	AC	23 ms 6,820 KB
testcase_53	AC	625 ms 7,744 KB
testcase_54	TLE	-
testcase_55	TLE	-
testcase_56	TLE	-
testcase_57	AC	2,262 ms 9,240 KB
testcase_58	AC	2,247 ms 9,240 KB
testcase_59	AC	698 ms 7,700 KB
testcase_60	TLE	-
testcase_61	TLE	-
testcase_62	TLE	-
testcase_63	TLE	-
testcase_64	TLE	-
testcase_65	TLE	-
testcase_66	AC	12 ms 6,820 KB
testcase_67	AC	13 ms 6,824 KB
testcase_68	TLE	-
testcase_69	TLE	-
testcase_70	TLE	-
testcase_71	TLE	-
testcase_72	TLE	-
testcase_73	TLE	-
testcase_74	TLE	-
testcase_75	AC	159 ms 6,820 KB
testcase_76	TLE	-
testcase_77	AC	2,495 ms 9,380 KB
testcase_78	TLE	-
testcase_79	TLE	-
testcase_80	TLE	-
testcase_81	TLE	-
testcase_82	AC	19 ms 6,820 KB
testcase_83	AC	2,403 ms 9,312 KB
testcase_84	AC	2,712 ms 9,376 KB
testcase_85	TLE	-
testcase_86	TLE	-
testcase_87	TLE	-
testcase_88	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

def setPrime(n, is_prime, primes):
	is_prime = [0] * (n + 1)
	for i in range(n + 1):
		is_prime[i] = True
	is_prime[0] = False
	is_prime[1] = False

	for i in range(n + 1):
		if (is_prime[i]):
			j = i * 2
			while (j <= n):
				is_prime[j] = False
				j += i

	for i in range(n + 1):
		if (is_prime[i]):
			primes.append(i)

n = int(input())
is_prime = []
primes = []
cnts = [0] * (3 * n + 1)

setPrime(3 * n, is_prime, primes)
primes2 = primes[:]

ans = 0
for c in primes:
	if (c > n):
		break
	for sum in primes2:
		ans += cnts[sum - c]
	primes2.remove(c)
	for a in primes:
		if (a >= c):
			break
		cnts[a + c] += 1
print(ans)

yukicoder

結果

テストケース

ソースコード