Submission #627593

---

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 < dp.GetLength(0); i++)
                for (int j = 0; j < dp.GetLength(1); 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

Judge Result