結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー aketijyuuzou
提出日時 2025-12-06 19:54:16
言語 C#
(.NET 8.0.404)
結果
TLE  
実行時間 -
コード長 4,324 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 10,340 ms
コンパイル使用メモリ 169,576 KB
実行使用メモリ 42,920 KB
最終ジャッジ日時 2025-12-06 19:54:31
合計ジャッジ時間 15,062 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 73
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (102 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff #
raw source code 

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

// No.3329 Only the Rightest Choice is Right!!!
// https://yukicoder.me/problems/no/3329
class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("4 5");
            WillReturn.Add("1 4 2 3");
            WillReturn.Add("1 4 2 3");
            //2
            //3 4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 3000");
            WillReturn.Add("1 1 1 1 1 1");
            WillReturn.Add("3000 3000 3000 3000 3000 3000");
            //1
            //6
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 3000");
            WillReturn.Add("2992 3000 1 1 1 1 1 1 1 1");
            WillReturn.Add("2992 3000 1 1 1 1 1 1 1 1");
            //1
            //2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long mW;

    struct ItemInfoDef
    {
        internal long Value;
        internal long Weight;
    }
    static List<ItemInfoDef> mItemInfoList = new List<ItemInfoDef>();

    static long mAnswer = long.MinValue;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        mW = wkArr[1];

        long[] ValueArr = GetSplitArr(InputList[1]);
        long[] WeightArr = GetSplitArr(InputList[2]);

        for (long I = 0; I <= ValueArr.GetUpperBound(0); I++) {
            ItemInfoDef WillAdd;
            WillAdd.Value = ValueArr[I];
            WillAdd.Weight = WeightArr[I];
            mItemInfoList.Add(WillAdd);
        }
        ExecDP();
        ExecDFS(0, 0, 0);

        Console.WriteLine(mAnswerList[mAnswerList.Count - 2]);
        Console.WriteLine(mAnswerList[mAnswerList.Count - 1]);
    }

    static long?[] mDPArr;

    static void ExecDP()
    {
        // 価値合計[重さ]なDP表
        mDPArr = new long?[mW + 1];
        mDPArr[0] = 0;

        foreach (ItemInfoDef EachItemInfo in mItemInfoList) {
            for (long I = mW; 0 <= I; I--) {
                if (mDPArr[I].HasValue == false) continue;

                long NewI = I + EachItemInfo.Weight;
                long NewVal = mDPArr[I].Value + EachItemInfo.Value;

                if (mW < NewI) continue;
                if (mDPArr[NewI].HasValue) {
                    if (mDPArr[NewI].Value >= NewVal) {
                        continue;
                    }
                }
                mDPArr[NewI] = NewVal;
                mAnswer = Math.Max(mAnswer, NewVal);
            }
        }
    }

    static HashSet<long> mIndSet = new HashSet<long>();
    static List<string> mAnswerList = new List<string>();

    static void ExecDFS(int CurrInd, long CurrWeight, long CurrSum)
    {
        if (CurrSum == mAnswer) {
            mAnswerList.Add(mIndSet.Count.ToString());
            var LongList = new List<long>();
            foreach (long EachInd in mIndSet.OrderBy(pX => pX)) {
                LongList.Add(EachInd + 1);
            }
            mAnswerList.Add(LongEnumJoin(" ", LongList));
        }

        for (int I = CurrInd; I <= mItemInfoList.Count - 1; I++) {
            long NewWeight = CurrWeight + mItemInfoList[I].Weight;
            long NewSum = CurrSum + mItemInfoList[I].Value;

            if (NewWeight > mW) continue;
            if (mDPArr[NewWeight].HasValue) {
                if (mDPArr[NewWeight] > NewSum) {
                    continue;
                }
            }
            mIndSet.Add(I);
            ExecDFS(I + 1, NewWeight, NewSum);
            mIndSet.Remove(I);
        }
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }

}
0