結果

問題 No.3014 岩井満足性問題
コンテスト
ユーザー aketijyuuzou
提出日時 2025-01-25 13:48:57
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,116 ms / 3,000 ms
コード長 2,719 bytes
コンパイル時間 5,390 ms
コンパイル使用メモリ 108,672 KB
実行使用メモリ 21,632 KB
最終ジャッジ日時 2025-01-25 23:00:03
合計ジャッジ時間 9,274 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge9
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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("5 3 20");
            WillReturn.Add("20 10 -15 30 20");
            WillReturn.Add("3 8 11 9 6");
            //60
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1 500");
            WillReturn.Add("3");
            WillReturn.Add("10");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("16 8 240");
            WillReturn.Add("101 -202 300 400 -430 700 -720 820 -830 -890 910 -970 990 1013 -1250 1270");
            WillReturn.Add("50 20 15 35 25 30 35 40 20 30 10 35 0 20 35 20");
            //4494
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long D = wkArr[1];
        long NeedCSum = wkArr[2];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long[] CArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        // 満足度[問題数,美しさ]なDP表
        long?[,] DPArr = new long?[D + 1, NeedCSum + 1];
        DPArr[0, 0] = 0;

        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            long CurrA = AArr[I];
            long CurrC = CArr[I];

            for (long J = DPArr.GetUpperBound(0); 0 <= J; J--) {
                long NewJ = J + 1;
                if (NewJ > DPArr.GetUpperBound(0)) continue;

                for (long K = DPArr.GetUpperBound(1); 0 <= K; K--) {
                    if (DPArr[J, K].HasValue == false) continue;

                    long NewK = K + CurrC;
                    NewK = Math.Min(NewK, DPArr.GetUpperBound(1));

                    long NewVal = DPArr[J, K].Value + CurrA;

                    if (DPArr[NewJ, NewK].HasValue) {
                        if (DPArr[NewJ, NewK] >= NewVal) {
                            continue;
                        }
                    }
                    DPArr[NewJ, NewK] = NewVal;
                }
            }
        }

        if (DPArr[DPArr.GetUpperBound(0), DPArr.GetUpperBound(1)].HasValue) {
            Console.WriteLine(DPArr[DPArr.GetUpperBound(0), DPArr.GetUpperBound(1)]);
        }
        else {
            Console.WriteLine("No");
        }
    }
}
0