結果

問題 No.385 カップ麺生活
ユーザー AreTrash
提出日時 2016-07-01 23:37:04
言語 C#
(csc 2.8.2.62916)
結果
AC  
実行時間 41 ms
コード長 2,554 Byte
コンパイル時間 628 ms
使用メモリ 18,132 KB
最終ジャッジ日時 2019-06-20 10:28:37

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 36 ms
16,084 KB
sample01.txt AC 36 ms
16,076 KB
sample02.txt AC 35 ms
16,080 KB
sample03.txt AC 35 ms
16,088 KB
system_test1.txt AC 35 ms
14,040 KB
system_test2.txt AC 36 ms
16,084 KB
system_test3.txt AC 36 ms
14,052 KB
system_test4.txt AC 36 ms
16,092 KB
test01.txt AC 33 ms
13,884 KB
test02.txt AC 37 ms
18,132 KB
test03.txt AC 35 ms
14,040 KB
test04.txt AC 37 ms
16,080 KB
test05.txt AC 36 ms
18,132 KB
test06.txt AC 37 ms
18,128 KB
z_gen_case1.txt AC 36 ms
16,084 KB
z_gen_case2.txt AC 35 ms
18,124 KB
z_gen_case3.txt AC 37 ms
16,076 KB
z_gen_case4.txt AC 35 ms
16,084 KB
z_gen_case5.txt AC 36 ms
16,088 KB
z_gen_case6.txt AC 41 ms
16,084 KB
z_gen_case7.txt AC 36 ms
16,100 KB
z_gen_case8.txt AC 34 ms
14,036 KB
z_gen_case9.txt AC 37 ms
18,124 KB
z_gen_case10.txt AC 37 ms
16,084 KB
z_gen_case11.txt AC 36 ms
18,124 KB
z_gen_case12.txt AC 37 ms
16,068 KB
z_gen_case13.txt AC 36 ms
16,076 KB
z_gen_case14.txt AC 37 ms
16,084 KB
z_gen_case15.txt AC 36 ms
18,128 KB
z_gen_case16.txt AC 36 ms
14,036 KB
z_gen_case17.txt AC 38 ms
16,088 KB
z_gen_case18.txt AC 35 ms
14,036 KB
z_gen_case19.txt AC 37 ms
16,096 KB
z_gen_case20.txt AC 37 ms
18,128 KB
テストケース一括ダウンロード
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 2.8.2.62916 (2ad4aabc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
using System;
using System.Collections.Generic;
using System.Linq;

namespace No385{
    public class Program{
        public static void Main(string[] args){
            var sr = new StreamReader();
            //---------------------------------
            var M = sr.Next<int>();
            var N = sr.Next<int>();
            var cn = sr.Next<int>(N);

            var pl = new List<int>();
            if(M > 1) {
                var nl = Enumerable.Range(2, M - 1).ToList();
                var sqrt = (int)Math.Sqrt(M);
                while(nl[0] <= sqrt) {
                    var prime = nl[0];
                    pl.Add(prime);
                    nl.RemoveAll(x => x % prime == 0);
                }
                pl.AddRange(nl);
            }


            var dp = new int[M + 1];
            dp[M] = 1;

            var tmp = new []{1};
            do{
                tmp = dp.ToArray();
                foreach(var c in cn.OrderByDescending(x => x)){
                    for(var i = M; i >= c; i--){
                        if(dp[i] >= 1) dp[i - c] = Math.Max(dp[i] + 1, dp[i - c]);
                    }
                }
            } while(!dp.SequenceEqual(tmp));

            var res = 0;
            foreach(var p in pl){
                if(dp[p] != 0) res += dp[p] - 1;
            }
            res += M / cn.Min();

            Console.WriteLine(res);
            //Console.WriteLine(string.Join(" ", dp));
            //---------------------------------
        }
    }

    public class StreamReader{
        private readonly char[] _c = {' '};
        private int _index = -1;
        private string[] _input = new string[0];

        public T Next<T>(){
            if(_index == _input.Length - 1){
                _index = -1;
                while(true){
                    string rl = Console.ReadLine();
                    if(rl == null){
                        if(typeof(T).IsClass) return default(T);
                        return (T)typeof(T).GetField("MinValue").GetValue(null);
                    }
                    if(rl != ""){
                        _input = rl.Split(_c, StringSplitOptions.RemoveEmptyEntries);
                        break;
                    }
                }
            }
            return (T)Convert.ChangeType(_input[++_index], typeof(T), System.Globalization.CultureInfo.InvariantCulture);
        }

        public T[] Next<T>(int x){
            var ret = new T[x];
            for(var i = 0; i < x; ++i) ret[i] = Next<T>();
            return ret;
        }
    }
}
0