Problem:


夜店(Night Market)  

太郎くんは，JOI 神社で開かれる夏祭りに行くことにした．

JOI 神社に向かう道に沿って，N 個の夜店が開かれている．それぞれの夜店には，1 からN までの番号が順番についており，遊んだ時の楽しさと遊ぶのにかかる時間がそれぞれ整数で決まっている．夜店i で遊んだ時の楽しさはAi で，夜店i で遊ぶのにかかる時間はBi である．

また，夏祭りのイベントとして花火大会があり，時刻S に最も大きな花火が打ち上げられる．太郎くんはこの最も大きな花火を見たいと思っている．

太郎くんは夜店と花火の両方を楽しむために，夏祭りに到着する時刻0 から夏祭りが終わる時刻T までの予定を立てることにした．

太郎くんは夜店の中からk 個(1 ≤ k ≤ N) の夜店を選び，それぞれに対して訪れる時刻を整数で決める．同じ夜店を2 度選ぶことはできない．選ばれた夜店の番号を小さい順にy1, y2, ... yk とし，夜店yi を訪れる時刻をxyi とすると，太郎くんは夜店yi で時刻xyi から時刻xyi + Byi まで遊ぶ．

太郎くんは夜店の番号の小さい順に遊び，同時に2 つの夜店では遊べない．また，夜店と夜店の間の移
動にかかる時間は無視できる．

時刻T を超えると夏祭りが終わるので，夜店で遊ぶことはできない．また，夜店で遊んでいる間は花火を見ることはできない．ただし，時刻S がある夜店で遊び始める時刻や遊び終わる時刻であった場合は，太郎くんは花火を見ることができるものとする．

すなわち，予定は以下の条件を満たしていなければならない．

 y1 < y2 < ... < yk

 xy1, xy2, ... xyk は整数．

 0 ≤ xy1 < xy1 + By1 ≤ xy2 < xy2 + By2 ≤ ... ≤ xyk < xyk + Byk ≤ T

 xyi < S < xyi + Byi となるようなi は存在しない．

選ばれた夜店の楽しさAy1, Ay2, ... Ayk の合計をM とする．太郎くんはM ができるだけ大きくなるように予定を立てたいと思っている．

課題

N 個の夜店の情報と時刻S, T が与えられた時，M の最大値を求めるプログラムを作成せよ．

制限

1 ≤ N ≤ 3000     夜店の数

1 ≤ T ≤ 3000     夏祭りが終わる時刻

0 ≤ S ≤ T     最も大きな花火が打ち上げられる時刻

0 ≤ Ai ≤ 100000 (= 105)     夜店i で遊んだ時の楽しさ

1 ≤ Bi ≤ 3000     夜店i で遊ぶのにかかる時間

入力

標準入力から以下の入力を読み込め．

入力の1 行目には整数N, T, S が空白を区切りとして書かれており，夜店の数がN 個，夏祭りが終わる時刻がT，最も大きな花火が打ち上げられる時刻がS であることを表す．

続くN 行には夜店の情報が書かれている．入力のi + 1 (1 ≤ i ≤ N) 行目には整数Ai, Bi が空白を区切りとして書かれており，夜店i で遊んだ時の楽しさがAi で，夜店i で遊ぶのにかかる時間がBi であることを表す．

また，すべての入力において，１つ以上の予定を立てられることが保証されている．

出力

標準出力に，M の最大値を表す整数を1 行で出力せよ．

採点基準

採点用データのうち，

配点の10%分については，N ≤ 20 を満たす．

配点の20%分については，S = 0 を満たす．

配点の30%分については，これら2 つの条件の少なくとも一方を満たす．また，これら2 つの条件の両方を満たすような採点用データはない．

入出力例

入力例 1

  

5 20 14
8 9
2 4
7 13
6 3
5 8

出力例 1
  

16

この例において，

夜店1 を時刻0 に訪れ，

夜店2 を時刻9 に訪れ，

夜店4 を時刻14 に訪れるような予定を立てると，M を最も大きくすることができる．

このとき，M = 8 + 2 + 6 = 16 である．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
5 20 14
8 9
2 4
7 13
6 3
5 8


Sample output:
16

Submission status: Wrong Answer

Solution code:
[N,T,S]=[int(x) for x in raw_input().split()]
items=[]
MbS=[[[-1,[]] for x in range(S+1)] for y in range(N+1)]
MaS=[[[-1,[]] for x in range(T-S+1)] for y in range(N+1)]
for i in range(N):
    items.append([int(x) for x in raw_input().split()])
def rec_dp(dp,j,w):
    if dp[j][w][0]!=-1:
        return dp[j][w]
    else:
        if j==N:
            res=[0,[]]
        elif w<items[j][1]:
            res=rec_dp(dp,j+1,w)
        else:
            plan1=rec_dp(dp,j+1,w)
            plan2a=rec_dp(dp,j+1,w-items[j][1])
            plan2=[plan2a[0]+items[j][0],plan2a[1]+[j]]
            if plan1[0]>plan2[0]:
                res=plan1
            else:
                res=plan2
        dp[j][w]=res
        return res
        
AA=rec_dp(MbS,0,S)

for s in AA[1]:
    reqtodel=items[s]
    items.remove(reqtodel)
N=N-len(AA[1])
AB=rec_dp(MaS,0,T-S)
print AA[0]+AB[0]

Submission status: Wrong Answer

Solution code:
[N,T,S]=[int(x) for x in raw_input().split()]
items=[]
MbS=[[[-1,[]] for x in range(S+1)] for y in range(N+1)]
MaS=[[[-1,[]] for x in range(T-S+1)] for y in range(N+1)]
for i in range(N):
    items.append([int(x) for x in raw_input().split()])
def rec_dp(dp,j,w):
    if dp[j][w][0]!=-1:
        return dp[j][w]
    else:
        if j==N:
            res=[0,[]]
        elif w<items[j][1]:
            res=rec_dp(dp,j+1,w)
        else:
            plan1=rec_dp(dp,j+1,w)
            plan2a=rec_dp(dp,j+1,w-items[j][1])
            plan2=[plan2a[0]+items[j][0],plan2a[1]+[j]]
            if plan1[0]>plan2[0]:
                res=plan1
            else:
                res=plan2
        dp[j][w]=res
        return res
AA=rec_dp(MbS,0,S)
deleted=[]
for s in AA[1]:
    reqtodel=items[s]
    items.remove(reqtodel)
    deleted.append(reqtodel)
N=N-len(AA[1])
AB=rec_dp(MaS,0,T-S)

N=N+len(AA[1])
items=items+deleted
MbS=[[[-1,[]] for x in range(S+1)] for y in range(N+1)]
MaS=[[[-1,[]] for x in range(T-S+1)] for y in range(N+1)]

BB=rec_dp(MaS,0,T-S)
deleted=[]
for s in BB[1]:
    reqtodel=items[s]
    items.remove(reqtodel)
    deleted.append(reqtodel)
N=N-len(BB[1])
BA=rec_dp(MbS,0,S)

print max(AA[0]+AB[0],BB[0]+BA[0])

Submission status: Wrong Answer

Solution code:
N, T, S = map(int, raw_input().split())
L = [map(int, raw_input().split()) for _ in xrange(N)]
dp = [0] * (T + 1)
for t, c in L:
    for i in xrange(T - c - 1, -1, -1):
        if i != S and (i + c) != S:
            dp[i + c] = max(dp[i + c], dp[i] + t)            
print max(dp)

Submission status: Wrong Answer

Solution code:
N, T, S = map(int, raw_input().split())
L = [map(int, raw_input().split()) for _ in xrange(N)]
dp = [0] * (T + 1)
for t, c in L:
    for i in xrange(T - c, -1, -1):
        if i > S or (i + c) < S:
            dp[i + c] = max(dp[i + c], dp[i] + t)
    ma = 0 if S == 0 else max(dp[:S])
    for i in xrange(T, S, -1):
        dp[i] = max(ma, dp[i])
print max(dp)

Submission status: Wrong Answer

Solution code:
N, T, S = map(int, raw_input().split())
L = [map(int, raw_input().split()) for _ in xrange(N)]
dp = [0] * (T + 1)
for t, c in L:
    for i in xrange(T - c, -1, -1):        
        if i > S or (i + c) < S:
            dp[i + c] = max(dp[i + c], dp[i] + t)
    for i in xrange(1, T + 1):
        dp[i] = max(dp[i], dp[i -1])
print max(dp)

Submission status: Wrong Answer

Solution code:
N, T, S = map(int, raw_input().split())
L = [map(int, raw_input().split()) for _ in xrange(N)]
dp = [[0] * (T + 1) for _ in xrange(N)]
count = 0
for n, (t, c) in enumerate(L):
    for i in xrange(T + 1):
        dp[n][i] = max(dp[n][i], dp[n-1][i])
        if i + c <= T and (i > S or i + c < S):
            dp[n][i+c] = max(dp[n-1][i + c], dp[n-1][i] + t)
        dp[n][i] = max(dp[n][i], dp[n][i-1])
print max(dp[N-1])

Submission status: Memory Limit Exceeded

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(10000)

input_lines = []
input_lines.append(raw_input())
N,T,S = [int(x) for x in input_lines[0].split(' ')]
data = []
for i in range(N):
	input_lines.append(raw_input())
	a,b = [int(x) for x in input_lines[i+1].split(' ')]
	data.append([a,b])
dp = [{}for i in range(N+1)]
judge = 0
judge2 = 0
def rec(i,t):
	global judge
	global judge2
	if judge2 == 1 and t < T-S:
		judge =1
	if dp[i].get(t) is not None:
		return dp[i].get(t)
	if i == N:
		res = 0
	elif t < data[i][1]:
		res = rec(i+1,t)
	else:
		if judge == 0 and t - data[i][1] < T-S and data[i][1] <= T-S:
			judge2 = 1
			res = max(rec(i+1,t),rec(i+1,T-S-data[i][1])+data[i][0])
			judge = 0
		elif judge == 0 and t - data[i][1] < T-S and data[i][1] > T-S:
			res = rec(i+1,t)
		else:
			res = max(rec(i+1,t),rec(i+1,t-data[i][1])+data[i][0])
	dp[i][t] = res
	return res

print rec(0,T)

Submission status: Accepted

Solution code:
# coding: utf-8

input_lines = []
input_lines.append(raw_input())
N,T,S = [int(x) for x in input_lines[0].split(' ')]
data = []
for i in range(N):
	input_lines.append(raw_input())
	a,b = [int(x) for x in input_lines[i+1].split(' ')]
	data.append([a,b])
dp = [[0 for i in range(T+1)]for j in range(N+1)]
judge = 0

for i in range(N-1,-1,-1):
	for j in range(0,T+1):
		#もうこの店で遊べないorSをはじめてまたいで，かつS以降に配置不可能
		if j < data[i][1] or (j > T-S and j - data[i][1] < T-S and data[i][1] > T-S):
			dp[i][j] = dp[i+1][j]
		#Sをはじめてまたいで，かつS以降に配置可能
		elif j > T-S and j - data[i][1] < T-S and data[i][1] <= T-S:
			dp[i][j] = max(dp[i+1][j],dp[i+1][T-S-data[i][1]]+data[i][0])
		else:
			dp[i][j] = max(dp[i+1][j],dp[i+1][j-data[i][1]]+data[i][0])

print dp[0][T]

Submission status: Accepted

Solution code:
n,t,s=map(int,raw_input().split())
ab=[map(int,raw_input().split()) for _ in xrange(n)]
dp=[[0]*(t+1) for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(1,t+1):
        if j<ab[i][1] or j-ab[i][1]<s<j:
            dp[i+1][j]=dp[i][j]
            continue
        dp[i+1][j]=max(dp[i][j],dp[i][j-ab[i][1]]+ab[i][0])
print(max(dp[n]))

Submission status: Accepted

Solution code:
n,t,s=map(int,raw_input().split())
ab=[map(int,raw_input().split()) for _ in xrange(n)]
dp=[[0]*(t+1) for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(1,t+1):
        if j<ab[i][1]:
            dp[i+1][j]=dp[i][j]
            continue
        if j-ab[i][1]<s<j:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j-1])
            continue
        dp[i+1][j]=max(dp[i][j],dp[i][j-ab[i][1]]+ab[i][0])
print(dp[n][t])

Submission status: Accepted

Solution code:
def solve():
    N, T, S = map(int, input().split())
    a = [tuple(map(int, input().split())) for _ in [0]*N]
    dp = {0: 0}
    
    for fun, time in a:
        for _t, _f in dp.copy().items():
            new_time = _t + time
            new_fun = fun + _f
            if _t < S < new_time:
                new_time = S + time
            if new_time <= T and (new_time not in dp or new_fun > dp[new_time]):
                dp[new_time] = new_fun

    print(max(dp.values()))


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def solve():
    N, T, S = map(int, input().split())
    a = [tuple(map(int, input().split())) for _ in [0]*N]
    dp = [float("-inf")]*(T+1)
    dp[0] = 0

    for fun, mise_time in a:
        for prev_time, from_fun, to_fun in zip(range(T-mise_time, -1, -1), dp[T-mise_time::-1], dp[::-1]):
            new_time = prev_time + mise_time
            new_fun = fun + from_fun
            if prev_time < S < new_time:
                new_time = S + mise_time
                if new_time > T:
                    continue
                to_fun = dp[new_time]
            if new_fun > to_fun:
                dp[new_time] = new_fun

    print(max(dp))


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def solve():
    N, T, S = map(int, input().split())
    a = [tuple(map(int, input().split())) for _ in [0]*N]
    dp = [float("-inf")]*(T+1)
    dp[0] = 0

    for fun, mise_time in a:
        for prev_time in range(T-mise_time, -1, -1):
            from_fun, to_fun = dp[prev_time], dp[prev_time+mise_time]
            new_time = prev_time + mise_time
            new_fun = fun + from_fun
            if prev_time < S < new_time:
                new_time = S + mise_time
                if new_time > T:
                    continue
                to_fun = dp[new_time]
            if new_fun > to_fun:
                dp[new_time] = new_fun

    print(max(dp))


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def solve():
    N, T, S = map(int, input().split())
    a = [tuple(map(int, input().split())) for _ in [0]*N]
    dp = [float("-inf")]*(T+1)
    dp[0] = 0

    for fun, mise_time in a:
        for prev_time, to_fun in zip(range(T-mise_time, -1, -1), dp[::-1]):
            new_time = prev_time + mise_time
            new_fun = fun + dp[prev_time]
            if prev_time < S < new_time:
                new_time = S + mise_time
                if new_time > T:
                    continue
                to_fun = dp[new_time]
            if new_fun > to_fun:
                dp[new_time] = new_fun

    print(max(dp))


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
  n, t, s = map(int, input().split())
  A = []
  B = []
  for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
  
  """
  dp[x + 1][y] ... 店xまででで時刻yまでの最大値
  dp[x + 1][y] = max(dp[x][y], dp[x + 1][y - 1], dp[x][y - B[x]] + A[x]) (not y - B[x] < s < y)
  dp[x + 1][y] = max(dp[x][y], dp[x + 1][y - 1])
  """
  
  dp = [[0] * (t + 1) for _ in range(n + 1)]
  for x in range(n):
    bx = B[x]
    ax = A[x]
    for y in range(1, t + 1):
      if 0 <= y - bx and (not (y - bx < s < y)):
        dp[x + 1][y] = max(dp[x][y], dp[x + 1][y - 1], dp[x][y - bx] + ax)
      else:
        dp[x + 1][y] = max(dp[x][y], dp[x + 1][y - 1])
  
  print(dp[n][t])

main()

Submission status: Accepted

Solution code:
def main():
  n, t, s = map(int, input().split())
  A = []
  B = []
  for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
  
  """
  dp[x + 1][y] ... 店xまででで時刻yまでの最大値
  dp[x + 1][y] = max(dp[x][y], dp[x + 1][y - 1], dp[x][y - B[x]] + A[x]) (not y - B[x] < s < y)
  dp[x + 1][y] = max(dp[x][y], dp[x + 1][y - 1])
  """

  dp = [[0] * (t + 1) for _ in range(n + 1)]
  for x in range(n):
    bx = B[x]
    ax = A[x]
    dpx = dp[x]
    dpx1 = dp[x + 1]
    for y in range(1, t + 1):
      if 0 <= y - bx and (not (y - bx < s < y)):
        dpx1[y] = max(dpx[y], dpx1[y - 1], dpx[y - bx] + ax)
      else:
        dpx1[y] = max(dpx[y], dpx1[y - 1])
   
  print(dp[n][t])
 
main()

Submission status: Accepted

Solution code:
N,T,S = map(int, input().split())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)

dp = [[0]*(T+1) for _ in range(N+1)]
for i in range(N):
  for j in range(1, T+1):
    if 0 <= j-B[i] and not(j-B[i] < S < j):
      dp[i+1][j] = max(dp[i][j], dp[i+1][j-1], dp[i][j-B[i]]+A[i])
    else:
      dp[i+1][j] = max(dp[i][j], dp[i+1][j-1])
 
print(dp[N][T])

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(10000)

input_lines = []
input_lines.append(raw_input())
N,T,S = [int(x) for x in input_lines[0].split(' ')]
data = []
for i in range(N):
	input_lines.append(raw_input())
	a,b = [int(x) for x in input_lines[i+1].split(' ')]
	data.append([a,b])
dp = [[0 for i in range(T+1)]for j in range(N+1)]
judge = 0
judge2 = 0
def rec(i,t):
	global judge
	global judge2
	if judge2 == 1 and t < T-S:
		judge =1
	if dp[i][t] != 0:
		return dp[i][t]
	if i == N:
		res = 0
	elif t < data[i][1] or (judge == 0 and t - data[i][1] < T-S and data[i][1] > T-S):
		res = rec(i+1,t)
	else:
		if judge == 0 and t - data[i][1] < T-S and data[i][1] <= T-S:
			judge2 = 1
			res = max(rec(i+1,t),rec(i+1,T-S-data[i][1])+data[i][0])
			judge = 0
		else:
			res = max(rec(i+1,t),rec(i+1,t-data[i][1])+data[i][0])
	dp[i][t] = res
	return res

print rec(0,T)

Submission status: Runtime Error

Solution code:
N, T, S = map(int, raw_input().split())
L = [map(int, raw_input().split()) for _ in xrange(N)]
dp = [[0] * (T + 1) for _ in xrange(N)]
for n in xrange(N):
    for t, c in L[:n + 1]:
        for i in xrange(S - c - 1, -1, -1):
            dp[n][i + c] = max(dp[n][i + c], dp[n][i] + t)

for n in xrange(N):
    dp[n][S + 1] = max(dp[n])
    for t, c in L[n + 1:]:
        for i in xrange(T - c, S, -1):
            dp[n][i + c] = max(dp[n][i + c], dp[n][i] + t)

print max(map(max, dp))

Submission status: Runtime Error

Solution code:
N, T, S = map(int, raw_input().split())
L = [map(int, raw_input().split()) for _ in xrange(N)]
dp = [0] * (T + 1)
for t, c in L:
    for i in xrange(T - c, -1, -1):
        if i > S or (i + c) < S:
            dp[i + c] = max(dp[i + c], dp[i] + t)
    ma = max(dp[:S])
    for i in xrange(T, S, -1):
        dp[i] = max(ma, dp[i])
print max(dp)