結果
問題 | No.458 異なる素数の和 |
ユーザー | Tanaka Yukio |
提出日時 | 2018-12-28 23:55:33 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 734 ms / 2,000 ms |
コード長 | 3,554 bytes |
コンパイル時間 | 2,279 ms |
コンパイル使用メモリ | 117,792 KB |
実行使用メモリ | 207,132 KB |
最終ジャッジ日時 | 2024-04-09 03:16:50 |
合計ジャッジ時間 | 26,359 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 712 ms
204,824 KB |
testcase_01 | AC | 712 ms
206,876 KB |
testcase_02 | AC | 714 ms
204,820 KB |
testcase_03 | AC | 707 ms
204,936 KB |
testcase_04 | AC | 707 ms
204,820 KB |
testcase_05 | AC | 708 ms
205,076 KB |
testcase_06 | AC | 707 ms
205,196 KB |
testcase_07 | AC | 706 ms
205,068 KB |
testcase_08 | AC | 734 ms
205,200 KB |
testcase_09 | AC | 707 ms
204,948 KB |
testcase_10 | AC | 706 ms
204,840 KB |
testcase_11 | AC | 709 ms
204,956 KB |
testcase_12 | AC | 711 ms
207,132 KB |
testcase_13 | AC | 708 ms
207,124 KB |
testcase_14 | AC | 708 ms
207,000 KB |
testcase_15 | AC | 709 ms
206,988 KB |
testcase_16 | AC | 734 ms
206,860 KB |
testcase_17 | AC | 709 ms
207,120 KB |
testcase_18 | AC | 707 ms
205,204 KB |
testcase_19 | AC | 707 ms
204,944 KB |
testcase_20 | AC | 707 ms
203,028 KB |
testcase_21 | AC | 707 ms
205,204 KB |
testcase_22 | AC | 713 ms
203,156 KB |
testcase_23 | AC | 712 ms
203,032 KB |
testcase_24 | AC | 714 ms
205,080 KB |
testcase_25 | AC | 711 ms
205,208 KB |
testcase_26 | AC | 711 ms
207,116 KB |
testcase_27 | AC | 711 ms
204,824 KB |
testcase_28 | AC | 710 ms
204,820 KB |
testcase_29 | AC | 709 ms
204,940 KB |
testcase_30 | AC | 709 ms
203,164 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
#pragma warning disable using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Runtime.Serialization.Formatters.Binary; using System.Text; using System.Text.RegularExpressions; using System.Diagnostics; using System.Numerics; using System.Collections; using System.Timers; static class MainClass { public static void Main(string[] args) { var N = Console.ReadLine().ToInt32(); var ls = GeneratePrimes().Take(2300).ToList(); var count = ls.Count(); var dp = new int[count + 10,20010]; for (int i = 0; i < count; i++) { for (int j = 0; j < 20010; j++) { dp[i, j] = -INF; } } dp[0, 0] = 0; for (int i = 0; i < count; i++) { for (int j = 0; j < 20010; j++) { var item = ls[i]; if (j - item < 0) { dp[i + 1, j] = dp[i, j]; } else { dp[i + 1, j] = Math.Max(dp[i, j], dp[i, j - ls[i]] + 1); } } } var num = dp[count, N]; Console.WriteLine(num < 0 ? -1 : num); } public class BoundedBoolArray { private BitArray _array; private int _lower; public BoundedBoolArray(int lower, int upper) { _array = new BitArray(upper - lower + 1); _lower = lower; } public bool this[int index] { get { return _array[index - _lower]; } set { _array[index - _lower] = value; } } } public static IEnumerable<int> GeneratePrimes() { var primes = new List<int>() { 2, 3 }; foreach (var p in primes) yield return p; int ix = 0; while (true) { int prime1st = primes[ix]; int prime2nd = primes[++ix]; var lower = prime1st * prime1st; var upper = prime2nd * prime2nd - 1; var sieve = new BoundedBoolArray(lower, upper); foreach (var prime in primes.Take(ix)) { var start = (int)Math.Ceiling((double)lower / prime) * prime; for (int index = start; index <= upper; index += prime) sieve[index] = true; } for (int i = lower; i <= upper; i++) { if (sieve[i] == false) { primes.Add(i); yield return i; } } } } #region ライブラリ public static long ToInt64(this string str) => long.Parse(str); public static int ToInt32(this string str) => int.Parse(str); public static BigInteger ToBigInteger(this string str) => BigInteger.Parse(str); public static List<string> SplittedStringToList(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).ToList(); public static List<int> SplittedStringToInt32List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToList(); public static List<BigInteger> SplittedStringToBigInteger(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => BigInteger.Parse(x)).ToList(); public const int INF = int.MaxValue / 2; #endregion }