結果
問題 |
No.910 素数部分列
|
ユーザー |
![]() |
提出日時 | 2020-03-15 20:36:57 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,241 bytes |
コンパイル時間 | 3,433 ms |
コンパイル使用メモリ | 78,148 KB |
実行使用メモリ | 59,236 KB |
最終ジャッジ日時 | 2024-11-25 10:18:43 |
合計ジャッジ時間 | 14,029 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 11 WA * 39 |
ソースコード
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Scanner; /** * Built using CHelper plug-in * Actual solution is at the top * * @author silviase */ public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; Scanner in = new Scanner(inputStream); PrintWriter out = new PrintWriter(outputStream); primeSubSequence solver = new primeSubSequence(); solver.solve(1, in, out); out.close(); } static class primeSubSequence { public void solve(int testNumber, Scanner in, PrintWriter out) { /* 3,5,7はすべて取り除いていい 考えるべきなのは - 11 - 19 をどうつくるか。 まず19を作ってから残りは11 左からの1の個数と右からの9の個数を考えていってminをとってそのmaxをとればいい。 残った1の数//2でわかるようになる */ int n = in.nextInt(); String s = in.next(); int l = s.length(); int res = 0; int[] one = new int[l + 1]; int[] nin = new int[l + 1]; int max = -1; for (int i = 0; i < l; i++) { if (s.charAt(i) == '3' || s.charAt(i) == '5' || s.charAt(i) == '7') { res++; } } one[0] = 0; for (int i = 0; i < l; i++) { if (s.charAt(i) == '1') { one[i + 1] = one[i] + 1; } else { one[i + 1] = one[i]; } } nin[n] = 0; for (int i = l - 1; i >= 0; i--) { if (s.charAt(i) == '9') { nin[i] = nin[i + 1] + 1; } else { nin[i] = nin[i + 1]; } } for (int i = 0; i <= n; i++) { max = Math.max(max, Math.min(one[i], nin[i])); } out.println(res + max + (one[n] - max) / 2); } } }