結果
問題 |
No.115 遠足のおやつ
|
ユーザー |
![]() |
提出日時 | 2017-01-12 08:27:13 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 2,339 ms / 5,000 ms |
コード長 | 2,681 bytes |
コンパイル時間 | 1,076 ms |
コンパイル使用メモリ | 108,032 KB |
実行使用メモリ | 329,300 KB |
最終ジャッジ日時 | 2025-01-03 01:20:43 |
合計ジャッジ時間 | 12,336 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections; using System.Collections.Generic; using System.Collections.Specialized; using System.Text; using System.Text.RegularExpressions; using System.Linq; using System.IO; class Program { static private Magatro M = new Magatro(); static private void Main(string[]args) { M.Scan(); M.Solve(); } } public class Scanner { private string[] S; private int Index; private char Separator; public Scanner(char separator = ' ') { Index = 0; Separator = separator; } private string[] Line() { return Console.ReadLine().Split(Separator); } public string Next() { string result; if (S == null || 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 class Magatro { private int N, D, K; public void Scan() { Scanner sc = new Scanner(); N = sc.NextInt(); D = sc.NextInt(); K = sc.NextInt(); } public void Solve() { //合計,N個目,N個買った Count[,,] dp = new Count[1001, 101, 101]; dp[0, 0, 0].Buy = new List<int>(); for (int i = 1; i <= N; i++) { for (int j = 0; j <= D; j++) { for (int k = 0; k < i; k++) { if (dp[j, i - 1, k].Buy == null) continue; Count cp = dp[j, i - 1, k].Copy(); dp[j, i, k] = Min(dp[j, i, k], cp); cp.Buy.Add(i); if (j + i > D) continue; dp[j + i, i, k + 1] = Min(cp, dp[j + i, i, k + 1]); } } } List<int> ans = dp[D, N, K].Buy; if (ans == null || ans.Count == 0) Console.WriteLine(-1); else Console.WriteLine(string.Join(" ",ans)); } private Count Min(Count a, Count b) { if (a.Buy == null) return b.Copy(); if (b.Buy == null) return a.Copy(); for (int i = 0; i < a.Buy.Count; i++) { if (a.Buy[i] < b.Buy[i]) return a.Copy(); else if (a.Buy[i] > b.Buy[i]) return b.Copy(); } return a.Copy(); } } public struct Count { public List<int> Buy; public Count Copy() { Count ret; ret.Buy = Buy.ToList(); return ret; } }