Submission #627594
Source Code Expand
using System; using System.Collections.Generic; using System.Linq; class Program { static string ReadLine() { return Console.ReadLine(); } static int ReadInt() { return int.Parse(ReadLine()); } static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); } static string[] ReadStrings() { return ReadLine().Split(); } struct D { public int w, v; } static int Calc(int W, int C, List<D>[] xxs) { var dp = new int[51, 100001]; // [色の種類, 重さ] var tmp = new int[51, 100001]; foreach (List<D> xs in xxs) { // Console.WriteLine("++"); for (int i = 0; i <= C; i++) for (int j = 0; j <= W; j++) tmp[i, j] = dp[i, j]; for (int c = C-1; c >= 0; c--) { for (int i = 0; i < xs.Count; i++) { for (int w = W; w-xs[i].w >= 0; w--) { tmp[c, w] = Math.Max(tmp[c, w], tmp[c, w - xs[i].w] + xs[i].v); } } } for (int c = C-1; c >= 0; c--) { for (int w = 0; w <= W; w++) { dp[c+1, w] = Math.Max(dp[c+1, w], tmp[c, w]); } } } return dp[C, W]; } static void Main() { var nwc = ReadInts(); int n = nwc[0], w = nwc[1], c = nwc[2]; var xxs = new List<D>[51]; for (int i = 0; i < xxs.Length; i++) xxs[i] = new List<D>(); for (int i = 0; i < n; i++) { var wvc = ReadInts(); xxs[wvc[2]-1].Add(new D { w = wvc[0], v = wvc[1] }); } Console.WriteLine(Calc(w, c, xxs)); } }
Submission Info
Submission Time | |
---|---|
Task | H - ナップザック |
User | noriok |
Language | C# (Mono 2.10.8.1) |
Score | 5 |
Code Size | 1778 Byte |
Status | AC |
Exec Time | 1227 ms |
Memory | 48856 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 5 / 5 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 05, 08, 09, 10, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 268 ms | 48732 KB |
01 | AC | 336 ms | 48784 KB |
02 | AC | 388 ms | 48792 KB |
03 | AC | 359 ms | 48768 KB |
04 | AC | 271 ms | 48792 KB |
05 | AC | 1227 ms | 48732 KB |
08 | AC | 263 ms | 48856 KB |
09 | AC | 415 ms | 48736 KB |
10 | AC | 1096 ms | 48768 KB |
90 | AC | 215 ms | 48736 KB |
91 | AC | 212 ms | 48724 KB |