結果
問題 | No.497 入れ子の箱 |
ユーザー |
![]() |
提出日時 | 2017-03-24 23:37:33 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,937 ms / 5,000 ms |
コード長 | 2,999 bytes |
コンパイル時間 | 2,381 ms |
コンパイル使用メモリ | 109,056 KB |
実行使用メモリ | 282,752 KB |
最終ジャッジ日時 | 2024-07-06 01:05:12 |
合計ジャッジ時間 | 47,338 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
コンパイルメッセージ
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.Generic; using System.Text; using System.Linq; class Program { public void Proc() { Reader.IsDebug = false; int hakoCount = int.Parse(Reader.ReadLine()); HakoList = new Hako[hakoCount]; for (int i = 0; i < hakoCount; i++) { HakoList[i] = new Hako(Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray()); } HakoList = HakoList.OrderByDescending(a => a.Tate).ThenByDescending(a => a.Yoko).ThenByDescending(a => a.Takasa).ToArray(); int ans = GetAns(0, HakoList[0].Tate+1, HakoList[0].Tate+1, HakoList[0].Tate+1); Console.WriteLine(ans); } private int GetAns(int idx, int tate, int yoko, int takasa) { if (idx >= HakoList.Length) { return 0; } if (!dic.ContainsKey(idx)) { dic.Add(idx, new Dictionary<int, Dictionary<int, Dictionary<int, int>>>()); } if (!dic[idx].ContainsKey(tate)) { dic[idx].Add(tate, new Dictionary<int, Dictionary<int, int>>()); } if(!dic[idx][tate].ContainsKey(yoko)) { dic[idx][tate].Add(yoko, new Dictionary<int,int>()); } if(dic[idx][tate][yoko].ContainsKey(takasa)) { return dic[idx][tate][yoko][takasa]; } int ans = 0; int ret = 0; if(HakoList[idx].Tate < tate && HakoList[idx].Yoko <yoko && HakoList[idx].Takasa < takasa) { ret = this.GetAns(idx+1, HakoList[idx].Tate, HakoList[idx].Yoko, HakoList[idx].Takasa); ans = Math.Max(ans, ret + 1); } ans = Math.Max(ans, GetAns(idx+1, tate, yoko, takasa)); dic[idx][tate][yoko][takasa] = ans; return ans; } private Dictionary<int, Dictionary<int, Dictionary<int, Dictionary<int, int>>>> dic = new Dictionary<int, Dictionary<int, Dictionary<int, Dictionary<int, int>>>>(); private Hako[] HakoList; private struct Hako { public int Tate; public int Yoko; public int Takasa; public Hako(int[] inpt) { int[] tmp = inpt.OrderByDescending(a => a).ToArray(); this.Tate = tmp[0]; this.Yoko = tmp[1]; this.Takasa = tmp[2]; } } public class Reader { public static bool IsDebug = true; private static String PlainInput = @" 4 2 2 2 1 1 1 3 3 3 4 1 4 "; private static System.IO.StringReader Sr = null; public static string ReadLine() { if (IsDebug) { if (Sr == null) { Sr = new System.IO.StringReader(PlainInput.Trim()); } return Sr.ReadLine(); } else { return Console.ReadLine(); } } } static void Main() { Program prg = new Program(); prg.Proc(); } }