Submission #3724249

---

Source Code Expand

using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		string[] input = Console.ReadLine().Split(' ');//Splitで区切り文字を指定して複数個受け取る。
		long n = long.Parse(input[0]);
		long w = long.Parse(input[1]);
    long[,] vertexes = new long[n,2];//ここに受け取る
    long[,,] dp = new long[n+1,n+1,3*n+1];//dp[見た数、とった数、超過の重さ] = 価値の最大値
    long answer = 0;
    for(long i = 0; i < n; i++)
    {
      long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);//１行ごとに受け取る
      vertexes[i,0] = nums[0];
      vertexes[i,1] = nums[1];
    }

    for(int i = 1; i <= n; i++)
    {
      for(int j = 0; j <= n; j++)
      {
        for(int k = 0; k <= 3*n; k++)
        {
          dp[i,j,k] = dp[i-1,j,k];//取らない場合
          if(j-1 >= 0 && k-(vertexes[i-1,0]-vertexes[0,0]) >= 0)
          {
            dp[i,j,k] = 
              Math.Max(dp[i,j,k],dp[i-1,j-1,k-(vertexes[i-1,0]-vertexes[0,0])] + vertexes[i-1,1]);
          }
        }
      }
    }
    
    for(int i = 0; i <= n; i++)
    {
      for(int j = 0; j <= n; j++)
      {
        for(int k = 0; k <= 3*n; k++)
        {
          if(vertexes[0,0]*j + k <= w)
            answer = Math.Max(dp[i,j,k], answer);
        }
      }
    }
    
		Console.WriteLine(answer);
	}
}

Submission Info

Judge Result