結果

問題 No.458 異なる素数の和
ユーザー zimphazimpha
提出日時 2017-04-02 14:51:23
言語 Java
(openjdk 23)
結果
AC  
実行時間 114 ms / 2,000 ms
コード長 2,229 bytes
コンパイル時間 1,922 ms
コンパイル使用メモリ 77,876 KB
実行使用メモリ 38,924 KB
最終ジャッジ日時 2024-07-08 00:07:37
合計ジャッジ時間 4,930 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*
* @author Chiaki.Hoshinomori
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task458 solver = new Task458();
solver.solve(1, in, out);
out.close();
}
static class Task458 {
public void solve(int testNumber, InputReader in, PrintWriter out) {
int n = in.nextInt();
int[] dp = new int[n + 1];
Arrays.fill(dp, -1);
boolean[] mark = new boolean[n + 1];
dp[0] = 0;
for (int i = 2; i <= n; i++) {
if (mark[i]) continue;
for (int j = n; j >= i; --j) {
if (dp[j - i] == -1) continue;
dp[j] = Math.max(dp[j], dp[j - i] + 1);
}
for (int j = i; j <= n; j += i) {
mark[j] = true;
}
}
out.println(dp[n]);
}
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0