結果

問題 No.385 カップ麺生活
ユーザー AreTrash
提出日時 2016-07-01 23:37:04
言語 C#
(csc 3.100.19.26603)
結果
AC  
実行時間 36 ms
コード長 2,554 Byte
コンパイル時間 616 ms
使用メモリ 10,036 KB
最終ジャッジ日時 2019-09-02 16:30:46

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 34 ms
10,000 KB
sample01.txt AC 34 ms
10,000 KB
sample02.txt AC 33 ms
10,000 KB
sample03.txt AC 34 ms
10,008 KB
system_test1.txt AC 35 ms
9,996 KB
system_test2.txt AC 34 ms
10,000 KB
system_test3.txt AC 34 ms
10,004 KB
system_test4.txt AC 34 ms
10,032 KB
test01.txt AC 32 ms
9,852 KB
test02.txt AC 36 ms
10,016 KB
test03.txt AC 34 ms
9,984 KB
test04.txt AC 34 ms
10,032 KB
test05.txt AC 35 ms
10,008 KB
test06.txt AC 35 ms
10,008 KB
z_gen_case1.txt AC 35 ms
10,004 KB
z_gen_case2.txt AC 35 ms
10,008 KB
z_gen_case3.txt AC 35 ms
9,996 KB
z_gen_case4.txt AC 35 ms
10,036 KB
z_gen_case5.txt AC 34 ms
10,024 KB
z_gen_case6.txt AC 36 ms
10,004 KB
z_gen_case7.txt AC 34 ms
10,000 KB
z_gen_case8.txt AC 36 ms
10,004 KB
z_gen_case9.txt AC 36 ms
10,004 KB
z_gen_case10.txt AC 35 ms
10,008 KB
z_gen_case11.txt AC 34 ms
10,004 KB
z_gen_case12.txt AC 36 ms
10,000 KB
z_gen_case13.txt AC 35 ms
10,004 KB
z_gen_case14.txt AC 35 ms
10,008 KB
z_gen_case15.txt AC 33 ms
10,008 KB
z_gen_case16.txt AC 34 ms
10,008 KB
z_gen_case17.txt AC 34 ms
10,024 KB
z_gen_case18.txt AC 35 ms
10,004 KB
z_gen_case19.txt AC 34 ms
10,008 KB
z_gen_case20.txt AC 36 ms
10,008 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