結果

問題 No.3014 岩井満足性問題
ユーザー 鳩でもわかるC#
提出日時 2025-01-28 14:38:36
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 786 ms / 3,000 ms
コード長 1,813 bytes
コンパイル時間 20,034 ms
コンパイル使用メモリ 175,540 KB
実行使用メモリ 217,544 KB
最終ジャッジ日時 2025-01-28 14:39:24
合計ジャッジ時間 22,022 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (153 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

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

class Program
{
    static string ReadLine()
    { 
        return Console.ReadLine().Trim();
    }

    static void Main()
    {
        int N, D, K;
        {
            int[] vs = ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            N = vs[0];
            D = vs[1];
            K = vs[2];
        }

        int[] A = ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int[] C = ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        long[,] dp = new long[D + 1, K + 1];
        for (int d = 0; d <= D; d++)
        {
            for (int k = 0; k <= K; k++)
                dp[d, k] = long.MinValue;
        }

        dp[0, 0] = 0;

        for (int i = 0; i < A.Length; i++)
        {
            long[,] nextdp = new long[D + 1, K + 1];
            for (int d = 0; d <= D; d++)
            {
                for (int k = 0; k <= K; k++)
                    nextdp[d, k] = long.MinValue;
            }

            for (int d = 0; d <= D; d++)
            {
                for (int k = 0; k <= K; k++)
                {
                    if (dp[d, k] == long.MinValue)
                        continue;

                    nextdp[d, k] = Math.Max(dp[d, k], nextdp[d, k]);
                    if(d >= D)
                        continue;

                    if (k + C[i] < K)
                        nextdp[d + 1, k + C[i]] = Math.Max(dp[d, k] + A[i], nextdp[d + 1, k + C[i]]);
                    else
                        nextdp[d + 1, K] = Math.Max(dp[d, k] + A[i], nextdp[d + 1, K]);
                }
            }
            dp = nextdp;
        }
        if(dp[D, K] > long.MinValue)
            Console.WriteLine(dp[D, K]);
        else
            Console.WriteLine("No");
    }
}
0