#458737 (Java21) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	37zigen
提出日時	2020-04-04 16:25:14
言語	Java21 (openjdk 21)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	1,416 bytes
コンパイル時間	2,385 ms
コンパイル使用メモリ	79,864 KB
実行使用メモリ	58,600 KB
最終ジャッジ日時	2024-07-03 07:27:27
合計ジャッジ時間	71,992 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	178 ms 44,488 KB
testcase_01	AC	175 ms 44,316 KB
testcase_02	AC	194 ms 45,068 KB
testcase_03	AC	194 ms 44,940 KB
testcase_04	AC	193 ms 45,176 KB
testcase_05	AC	194 ms 44,788 KB
testcase_06	AC	192 ms 44,976 KB
testcase_07	AC	196 ms 45,356 KB
testcase_08	AC	188 ms 45,108 KB
testcase_09	AC	195 ms 44,780 KB
testcase_10	AC	195 ms 45,180 KB
testcase_11	AC	194 ms 45,164 KB
testcase_12	AC	195 ms 44,736 KB
testcase_13	AC	196 ms 45,076 KB
testcase_14	AC	196 ms 44,924 KB
testcase_15	AC	195 ms 45,120 KB
testcase_16	AC	196 ms 45,240 KB
testcase_17	AC	196 ms 45,104 KB
testcase_18	AC	194 ms 44,856 KB
testcase_19	AC	194 ms 45,096 KB
testcase_20	AC	209 ms 44,928 KB
testcase_21	AC	263 ms 45,068 KB
testcase_22	AC	255 ms 45,088 KB
testcase_23	AC	205 ms 45,084 KB
testcase_24	AC	206 ms 45,188 KB
testcase_25	AC	294 ms 45,292 KB
testcase_26	AC	270 ms 45,248 KB
testcase_27	AC	215 ms 45,244 KB
testcase_28	AC	217 ms 45,272 KB
testcase_29	AC	239 ms 45,392 KB
testcase_30	AC	238 ms 44,984 KB
testcase_31	AC	256 ms 45,236 KB
testcase_32	AC	275 ms 45,084 KB
testcase_33	AC	273 ms 45,368 KB
testcase_34	AC	273 ms 44,960 KB
testcase_35	AC	262 ms 45,136 KB
testcase_36	AC	266 ms 45,252 KB
testcase_37	AC	207 ms 45,004 KB
testcase_38	AC	209 ms 45,236 KB
testcase_39	AC	263 ms 45,252 KB
testcase_40	AC	267 ms 45,292 KB
testcase_41	AC	260 ms 45,356 KB
testcase_42	AC	258 ms 45,252 KB
testcase_43	AC	260 ms 45,084 KB
testcase_44	AC	262 ms 45,192 KB
testcase_45	AC	219 ms 45,220 KB
testcase_46	AC	219 ms 45,300 KB
testcase_47	AC	223 ms 45,216 KB
testcase_48	AC	292 ms 45,240 KB
testcase_49	AC	293 ms 45,268 KB
testcase_50	AC	260 ms 45,248 KB
testcase_51	AC	258 ms 45,120 KB
testcase_52	AC	223 ms 45,116 KB
testcase_53	AC	484 ms 46,068 KB
testcase_54	AC	1,809 ms 46,104 KB
testcase_55	AC	1,817 ms 46,356 KB
testcase_56	AC	1,812 ms 46,464 KB
testcase_57	AC	759 ms 45,968 KB
testcase_58	AC	755 ms 46,040 KB
testcase_59	AC	497 ms 45,972 KB
testcase_60	AC	927 ms 45,828 KB
testcase_61	AC	929 ms 45,960 KB
testcase_62	AC	2,142 ms 46,128 KB
testcase_63	AC	1,294 ms 46,128 KB
testcase_64	AC	1,066 ms 46,380 KB
testcase_65	AC	1,057 ms 46,312 KB
testcase_66	AC	198 ms 45,252 KB
testcase_67	AC	205 ms 45,244 KB
testcase_68	AC	1,968 ms 46,088 KB
testcase_69	AC	1,959 ms 46,092 KB
testcase_70	AC	1,824 ms 46,056 KB
testcase_71	AC	1,832 ms 46,448 KB
testcase_72	AC	1,241 ms 45,952 KB
testcase_73	AC	2,907 ms 46,508 KB
testcase_74	AC	2,904 ms 46,520 KB
testcase_75	AC	287 ms 45,136 KB
testcase_76	AC	1,932 ms 46,076 KB
testcase_77	AC	789 ms 45,860 KB
testcase_78	AC	2,468 ms 46,244 KB
testcase_79	AC	1,985 ms 46,536 KB
testcase_80	AC	2,294 ms 46,428 KB
testcase_81	AC	1,837 ms 46,060 KB
testcase_82	AC	214 ms 45,280 KB
testcase_83	AC	768 ms 46,152 KB
testcase_84	AC	824 ms 46,032 KB
testcase_85	AC	1,713 ms 46,268 KB
testcase_86	AC	2,309 ms 46,188 KB
testcase_87	TLE	-
testcase_88	TLE	-

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

ソースコード

raw source code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		long curtime=System.currentTimeMillis();
		new Main().run();
		System.err.println(System.currentTimeMillis()-curtime);
	}
	
	int MAX=300001;
	boolean[] isPrime=new boolean[MAX];
	ArrayList<Integer> primes=new ArrayList<>();
	{
		Arrays.fill(isPrime, true);
		isPrime[0]=isPrime[1]=false;
		for(int i=2;i<isPrime.length;++i) {
			if(!isPrime[i])continue;
			primes.add(i);
			for(int j=2*i;j<isPrime.length;j+=i)
				isPrime[j]=false;
		}
	}
	
	void run() {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();//5<=N<=1e5
		long[] dp=new long[MAX];
		for(int p:primes) {
			if(p>N)break;
			for(int q:primes) {
				if(q>N)break;
				++dp[p+q];
			}
		}
		
		long ans=0;
		int src=0;
		for(int p:primes) {
			if(p>N)break;
			while(src<primes.size()&&primes.get(src)-p<=0)++src;
			for(int i=src;i<primes.size();++i) {
				int target=primes.get(i);
				if(target-p<=0)continue;
				ans+=dp[target-p];
			}
		}
		//a+b+c が　素数　かつ　a==b==c　は存在しない。
		for(int p:primes) {
			if(p>N)break;
			for(int q:primes) {
				if(q>N)break;
				if(isPrime[p+p+q]) {
					ans-=3;
				}
			}
		}
		if(ans%6!=0)throw new AssertionError();
		System.out.println(ans/6);
	}
	
	void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}
}

yukicoder

結果

テストケース

ソースコード