結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2016-05-28 03:20:38 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 76 ms / 5,000 ms |
コード長 | 2,489 bytes |
コンパイル時間 | 2,407 ms |
コンパイル使用メモリ | 108,800 KB |
実行使用メモリ | 19,584 KB |
最終ジャッジ日時 | 2024-10-07 17:12:23 |
合計ジャッジ時間 | 3,881 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
コンパイルメッセージ
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[] inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();ItemCount = inpt[0];int inputCount = inpt[1];for(int i=0; i<inputCount; i++) {inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();if(!pointDic.ContainsKey(inpt[1])) {pointDic.Add(inpt[1], new Dictionary<int,long>());}pointDic[inpt[1]].Add(inpt[0], inpt[2]);}long ans = this.GetAns(0, this.ItemCount);Console.WriteLine(ans);}private int ItemCount = 0;private Dictionary<int, long> dic = new Dictionary<int, long>();private long GetAns(int flag, int remain) {if(dic.ContainsKey(flag)) {return dic[flag];}if(remain == 0) {return 0;}long ans = 0;for(int i=0; i<ItemCount; i++) {int key = 1<<i;if((flag & key) == key) {continue;}long p = 0;if(pointDic.ContainsKey(i)) {foreach (int tmp in pointDic[i].Keys){int subKey = 1<<tmp;if((flag & subKey) == subKey) {p+=pointDic[i][tmp];}}}long ret = this.GetAns(flag + key, remain - 1);ret += p;ans = Math.Max(ans, ret);}dic.Add(flag, ans);return ans;}private Dictionary<int, Dictionary<int, long>> pointDic = new Dictionary<int, Dictionary<int, long>>();public class Reader{public static bool IsDebug = true;private static String PlainInput = @"";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();}}