ABC195-D Shipping Center

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 4 3");
            WillReturn.Add("1 9");
            WillReturn.Add("5 3");
            WillReturn.Add("7 8");
            WillReturn.Add("1 8 6 9");
            WillReturn.Add("4 4");
            WillReturn.Add("1 4");
            WillReturn.Add("1 3");
            //20
            //0
            //9
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct NimotuInfoDef
    {
        internal int W;
        internal int V;
    }
    static List<NimotuInfoDef> mNimotuInfoList = new List<NimotuInfoDef>();

    static int[] mXArr;

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        int N = wkArr[0];

        foreach (string EachStr in InputList.Skip(1).Take(N)) {
            SplitAct(EachStr);
            NimotuInfoDef WillAdd;
            WillAdd.W = wkArr[0];
            WillAdd.V = wkArr[1];
            mNimotuInfoList.Add(WillAdd);
        }
        // Breakを使いたいので、大きさの昇順にソート
        mNimotuInfoList = mNimotuInfoList.OrderBy(pX => pX.W).ToList();

        mXArr = InputList[N + 1].Split(' ').Select(pX => int.Parse(pX)).ToArray(); ;

        foreach (string EachStr in InputList.Skip(1 + N + 1)) {
            SplitAct(EachStr);
            ExecQuery(wkArr[0], wkArr[1]);
        }
    }

    // クエリを処理する
    static void ExecQuery(int pL, int pR)
    {
        // 使用不能番号を除外
        var XList = new List<int>(mXArr);
        for (int I = pR; pL <= I; I--) {
            XList.RemoveAt(I - 1);
        }

        // 箱の大きさの昇順にソートする
        XList.Sort();

        // 使用済の荷物
        var UsedNimotuIndSet = new HashSet<int>();

        int Answer = 0;
        foreach (int EachLong in XList) {
            bool Found = false;
            int UseNimotuInd = -1;
            int UseNimotuV = int.MinValue;

            for (int I = 0; I <= mNimotuInfoList.Count - 1; I++) {
                if (EachLong < mNimotuInfoList[I].W) break;
                if (UsedNimotuIndSet.Contains(I)) continue;

                if (UseNimotuV < mNimotuInfoList[I].V) {
                    UseNimotuV = mNimotuInfoList[I].V;
                    UseNimotuInd = I;
                    Found = true;
                }
            }
            if (Found) {
                UsedNimotuIndSet.Add(UseNimotuInd);
                Answer += UseNimotuV;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

箱、荷物、クエリが全て50以下で、制約が緩いので
箱ごとに、ナイーブに貪欲法を使ってます。