結果
問題 | No.385 カップ麺生活 |
ユーザー |
![]() |
提出日時 | 2017-03-29 22:44:25 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 3,050 bytes |
コンパイル時間 | 1,722 ms |
コンパイル使用メモリ | 114,692 KB |
実行使用メモリ | 27,360 KB |
最終ジャッジ日時 | 2024-10-04 22:55:00 |
合計ジャッジ時間 | 3,499 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Linq;using System.Collections;using System.Collections.Generic;using System.IO;class Program{static void Main(){new Magatro().Solve();}}public class Scanner{private StreamReader Sr;private string[] S;private int Index;private const char Separator = ' ';public Scanner(Stream source){Index = 0;S = new string[0];Sr = new StreamReader(source);}private string[] Line(){return Sr.ReadLine().Split(Separator);}public string Next(){string result;if (Index >= S.Length){S = Line();Index = 0;}result = S[Index];Index++;return result;}public int NextInt(){return int.Parse(Next());}public double NextDouble(){return double.Parse(Next());}public long NextLong(){return long.Parse(Next());}public decimal NextDecimal(){return decimal.Parse(Next());}public string[] StringArray(int index = 0){Next();Index = S.Length;return S.Skip(index).ToArray();}public int[] IntArray(int index = 0){return StringArray(index).Select(int.Parse).ToArray();}public long[] LongArray(int index = 0){return StringArray(index).Select(long.Parse).ToArray();}public bool EndOfStream{get { return Sr.EndOfStream; }}}public class Magatro{private int M;private int N;private int[] C;private int[] Arr;private int[] Primes;private void Scan(){var cin = new Scanner(Console.OpenStandardInput());M = cin.NextInt();N = cin.NextInt();C = cin.IntArray();}private void PrimeCalc(){bool[] num = new bool[M + 1];num[0] = true;num[1] = true;for (int i = 2; i * i <= M; i++){if (!num[i]){for (int j = i + i; j <= M; j += i){num[j] = true;}}}var list = new List<int>();for (int i = 0; i <= M; i++){if (!num[i]){list.Add(i);}}Primes = list.ToArray();}public void Solve(){Scan();Arr = (new int[M + 1]).Select(i => -1).ToArray();Arr[M] = 0;for (int i = M; i >= 0; i--){if (Arr[i] == -1) continue;foreach (int j in C){if (i - j < 0) continue;Arr[i - j] = Math.Max(Arr[i - j], Arr[i] + 1);}}PrimeCalc();int ans = 0;foreach(int i in Primes){if (Arr[i] == -1) continue;ans += Arr[i];}ans += Arr.Max();Console.WriteLine(ans);}}