Problem:


Problem D:THE BYDOLM@STER

Description

 -->

THE BYDOLM@STER(バイドルマスター)とは1rem社より2010/4/1にEXIDNAで発売が予定されている育成シミュレーションゲームである。一応断っておくが、今月初めにネットワーク接続サービスが停止した某アーケードゲームとはたぶん関係が無い。

このゲームはバイドルたちからプロデュースするユニット(編隊)のメンバーを選択し、メンバーたちとのレッスンやコミュニケーションを通じて、彼女(彼)らをバイドルの頂点、トップバイドルに育て上げるゲームである。

各バイドルには能力値としてボーカル、ダンス、ルックスの3つのパラメータを持ち、ユニットの能力値はユニットに属している全てのバイドルのパラメータの合計値となる。ユニットの3つの能力値のうち最大の物がユニットのランクとなる。

ユニットに人数制限は無く、メンバーの人数が1体でも、3体でも、100体でもユニットとして活動できる。もちろん同じバイドルを複数雇うこと出来るが、バイドルを雇うためには費用がかかるのでこれを考慮に入れなければならない。

プロデューサーであるあなたは最高のユニットを作るためにプログラムを書いて計算することにした。

Input

入力は複数のテストケースからなる。

各テストケースの1行目にはバイドルの数Nと使用可能な費用Mが与えられる。(1<=N,M<=300)
次の2*N行には各バイドルに関しての情報が書かれている。

バイドルの情報の1行目にはバイドルの名前。バイドルの名前はアルファベットと空白から成り、30文字を以下である。また同一名のバイドルは存在しない。

2行目には整数C、V、D、Lが与えられる。Cはそのバイドルを1体雇用するコスト、Vはボーカル、Dはダンス、Lはルックスの能力値を表す。(1<=C,V,D,L<=300)

入力はEOFで終わる。

Output

与えられた費用の中で作れるユニットのランクの最大値を答えよ。

ユニットが作れない場合は0を出力せよ。

Sample Input

3 10
Dobkeradops
7 5 23 10
PataPata
1 1 2 1
dop
5 3 11 14
2 300
Bydo System Alpha
7 11 4 7
Green Inferno
300 300 300 300

Output for Sample Input

29
462



Sample input:
3 10
Dobkeradops
7 5 23 10
PataPata
1 1 2 1
dop
5 3 11 14
2 300
Bydo System Alpha
7 11 4 7
Green Inferno
300 300 300 300


Sample output:
29
462

Submission status: Wrong Answer

Solution code:
while 1:
	try:
		N,M = map(int,raw_input().split())
		bidol = []
		for i in range(N):
			name = raw_input()
			bidol.append(map(int,raw_input().split()))

		ans = 0
		for VDL in range(3):
			bidol = sorted(bidol, key = lambda x:x[1+VDL]*1.0/x[0])
			for i in range(N):
				V = D = L = cost = 0
				for j in range(i,N):
					if cost + bidol[j][0] <= M:
						num = (M-cost)/bidol[j][0]
						cost += num*bidol[j][0]
						V += num*bidol[j][1]
						D += num*bidol[j][2]
						L += num*bidol[j][3]
				ans = max(ans,V,D,L)
		print ans
	except:
		break

Submission status: Wrong Answer

Solution code:
while 1:
	try:
		N,M = map(int,raw_input().split())
		dp = [[0]*(M+1) for i in range(3)]
		for _ in range(N):
			name = raw_input()
			C,V,D,L = map(int,raw_input().split())
			VDL = [V,D,L]
			for i in range(3):
				dp[i][C] = max(dp[i][C],VDL[i])
				for j in range(M):
					if dp[i][j]:
						try: dp[i][j+C] = max(dp[i][j+C],dp[i][j]+VDL[i])
						except: break
		print max(max(dp[0]),max(dp[1]),max(dp[2]))
	except:
		break

Submission status: Accepted

Solution code:
while True:
  try:
    n, m = map(int, input().split())
  except EOFError:
    break
  costs = []
  vocals = []
  dances = []
  looks = []
  for _ in range(n):
    input()
    c, v, d, l = map(int, input().split())
    costs.append(c)
    vocals.append(v)
    dances.append(d)
    looks.append(l)
  
  def max_param(params):
    dp = [0] * (m + 1)
    for i in range(n):
      c = costs[i]
      p = params[i]
      for j in range(m - c + 1):
        dp[j + c] = max(dp[j + c], dp[j] + p)
    return dp[-1]

  print(max(max_param(vocals), max_param(dances), max_param(looks)))

Submission status: Accepted

Solution code:
while(1):
    try:
        N,M=map( int,raw_input().split())
        W=[[] for i in range(3)]
        for i in range(N):
            name=raw_input()
            inp=map( int,raw_input().split())
            c=inp[0]
            for i in range(3):
                W[i].append([c, inp[1+i]])
        for i in range(3):
            W[i].sort(key = lambda x:x[0])
        ans=0
        for i in range(3):
            U=[0 for x in range(M+1)]
            V=[0 for x in range(M+1)]
            for y in range(N):
                for t in range(M+1):
                    ci=W[i][y][0]*t
                    if ci <= M:
                        U[ci]=max(U[ci], W[i][y][1]*t)
                    else:
                        break
            for j in range(M+1):
                for k in range(j+1):
                    V[j]=max(V[j], V[j-k]+U[k])
            ans=max(ans, V[-1])
        print ans
    except:
        break

Submission status: Accepted

Solution code:
while 1:
	try:
		N,M = map(int,raw_input().split())
		dp = [[0]*(M+1) for i in range(3)]
		for _ in range(N):
			name = raw_input()
			C,V,D,L = map(int,raw_input().split())
			VDL = [V,D,L]
			for i in range(3):
				try: dp[i][C] = max(dp[i][C],VDL[i])
				except: pass
				for j in range(M):
					if dp[i][j]:
						try: dp[i][j+C] = max(dp[i][j+C],dp[i][j]+VDL[i])
						except: break
		print max(max(dp[0]),max(dp[1]),max(dp[2]))
	except:
		break

Submission status: Accepted

Solution code:
while 1:
	try:
		N,M = map(int,raw_input().split())
		dp = [[0]*(M+1) for i in range(3)]
		for _ in range(N):
			name = raw_input()
			C,V,D,L = map(int,raw_input().split())
			VDL = [V,D,L]
			for i in range(3):
				try: dp[i][C] = max(dp[i][C],VDL[i])
				except: break
				for j in range(M):
					if dp[i][j]:
						try: dp[i][j+C] = max(dp[i][j+C],dp[i][j]+VDL[i])
						except: break
		print max(max(dp[0]),max(dp[1]),max(dp[2]))
	except:
		break

Submission status: Accepted

Solution code:
while 1:
	try:
		N,M = map(int,raw_input().split())
		dp = [[0]*(M+1) for i in range(3)]
		for _ in range(N):
			name = raw_input()
			C,V,D,L = map(int,raw_input().split())
			VDL = [V,D,L]
			if C > M:
				continue
			for i in range(3):
				dp[i][C] = max(dp[i][C],VDL[i])
				for j in range(M):
					if dp[i][j]:
						if j+C <= M:
							dp[i][j+C] = max(dp[i][j+C],dp[i][j]+VDL[i])
		print max(max(dp[0]),max(dp[1]),max(dp[2]))
	except:
		break

Submission status: Accepted

Solution code:
while 1:
	try:
		N,M = map(int,raw_input().split())
		dp = [[0]*(M+1) for i in range(3)]
		for _ in range(N):
			name = raw_input()
			C,V,D,L = map(int,raw_input().split())
			VDL = [V,D,L]
			if C > M:
				continue
			for i in range(3):
				dp[i][C] = max(dp[i][C],VDL[i])
				for j in range(M-C+1):
					if dp[i][j]:
						dp[i][j+C] = max(dp[i][j+C],dp[i][j]+VDL[i])
		print max(max(dp[0]),max(dp[1]),max(dp[2]))
	except:
		break

Submission status: Accepted

Solution code:
while 1:
	try:
		N,M = map(int,raw_input().split())
		dp = [[0]*(M+1) for i in range(3)]
		bidols = [[raw_input()]+map(int,raw_input().split()) for i in range(N)]
		for bidol in bidols:
			C = bidol[1]
			if C > M:
				continue
			for i in range(3):
				dp[i][C] = max(dp[i][C],bidol[i+2])
				for j in range(M-C+1):
					if dp[i][j]:
						dp[i][j+C] = max(dp[i][j+C],dp[i][j]+bidol[i+2])
		print max(max(dp[0]),max(dp[1]),max(dp[2]))
	except:
		break

Submission status: Runtime Error

Solution code:
while(1):
    try:
        N,M=map( int,raw_input().split())
        W=[[] for i in range(3)]
        for i in range(N):
            name=raw_input()
            inp=map( int,raw_input().split())
            c=inp[0]
            for i in range(3):
                W[i].append([c, inp[1+i]])

        ans=0
        for i in range(3):
            DP=[[0 for x in range(M+1)] for y in range(N)]

            for t in range(M):
                ci=W[i][0][0]*t
                if ci <= M:
                    DP[0][ci]=W[i][0][1]*t
                else:
                    break

            for y in range(1,N):
                for x in range(M+1):

                    for t in range(M):
                        ci=W[i][y][0]*t
                        if ci <= x:
                            DP[y][x] = max(DP[y][x], DP[y-1][x-ci]+W[i][y][1]*t )
                        else:
                            break
            ans=max(ans, max(DP[-1]))
        print ans
    except:
        break

Submission status: Runtime Error

Solution code:
while(1):
    try:
        N,M=map( int,raw_input().split())
        W=[[] for i in range(3)]
        for i in range(N):
            name=raw_input()
            inp=map( int,raw_input().split())
            c=inp[0]
            for i in range(3):
                W[i].append([c, inp[1+i]])
        for i in range(3):
            W[i].sort(key = lambda x:x[0])
        ans=0
        for i in range(3):
            DP=[[0 for x in range(M+1)] for y in range(N)]

            for t in range(M+1):
                ci=W[i][0][0]*t
                if ci <= M:
                    DP[0][ci]=W[i][0][1]*t
                else:
                    break

            for y in range(1,N):
                for x in range(M+1):
                    for t in range(M):
                        ci=W[i][y][0]*t
                        if ci <= x:
                            DP[y][x] = max(DP[y][x], DP[y-1][x-ci]+W[i][y][1]*t )
                        else:
                            break
            ans=max(ans, max(DP[-1]))
        print ans
    except:
        break