Problem:


暑い日々 (Hot days) 

  問題

日本が冬であるこの時期，南半球にあるオーストラリアでは暑い日が続いている．オーストラリアに住む IOI 君は，ある D 日間の天気予報をもとに，着る服の計画を立てることにした．i 日目 (1 ≦ i ≦ D) の最高気温は Ti 度であると予報されている．

IOI 君は N 種類の服を持っており，それらには 1 から N までの番号がついている．服 j (1 ≦ j ≦ N) は最高気温が Aj 度以上 Bj 度以下の日に着るのに適している．また，それぞれの服には「派手さ」とよばれる整数が定まっており，服 j の派手さは Cj である．

D 日間のそれぞれに対し，IOI 君は，最高気温が天気予報に従ったときに着るのに適した服のうち 1 つを着る服として選ぶ．同じ服を何度選んでもよいし，D 日間で一度も選ばれない服があってもよい．

似ている服を連続して着ることをなるべく避けようと思った IOI 君は，連続する日に着る服の派手さの差の絶対値の合計をできるだけ大きくしようと考えた．すなわち，i 日目に服 xi を選んだとして，値 |Cx1 - Cx2| + |Cx2 - Cx3| + … + |CxD-1 - CxD| を最大にしたい．この最大値を求めるプログラムを作成せよ．

  入力

入力は 1 + D + N 行からなる．

1 行目には，2 つの整数 D, N (2 ≦ D ≦ 200，1 ≦ N ≦ 200) が空白を区切りとして書かれている．D は服の計画を立てる日数，N は IOI 君が持っている服の種類の数を表す．

続く D 行のうちの i 行目 (1 ≦ i ≦ D) には，1 つの整数 Ti (0 ≦ Ti ≦ 60) が書かれている．これは，i 日目の最高気温が Ti 度であると予報されていることを表す．

続く N 行のうちの j 行目 (1 ≦ j ≦ N) には，3 つの整数 Aj, Bj, Cj (0 ≦ Aj ≦ Bj ≦ 60，0 ≦ Cj ≦ 100) が書かれている．これらは，服 j は最高気温が Aj 度以上 Bj 度以下の日に着るのに適しており，派手さが Cj であることを表す．

最高気温が天気予報に従ったときに着るのに適した服が，D 日間のどの日に対しても 1 つ以上存在することが保証されている．

  出力

連続する日に着る服の派手さの差の絶対値の合計，すなわち，値 |Cx1 - Cx2| + |Cx2 - Cx3| + … + |CxD-1 - CxD| の最大値を 1 行で出力せよ．

 入出力例

入力例 1

  

3 4
31
27
35
20 25 30
23 29 90
21 35 60
28 33 40

出力例 1

   

80

入出力例 1 において，1 日目の服の候補は服 3 と服 4 であり，2 日目の服の候補は服 2 と服 3 であり，3 日目の服の候補は服 3 のみである．1 日目に服 4 を，2 日目に服 2 を，3 日目に服 3 を選ぶ．すなわち，x1 = 4，x2 = 2，x3 = 3 とする．このとき，1 日目と 2 日目の服の派手さの差の絶対値は |40 - 90| = 50 であり，2 日目と 3 日目の服の派手さの差の絶対値は |90 - 60| = 30 である．合計は 80 となり，これが最大値である．

入力例 2
  

  

5 2
26
28
32
29
34
30 35 0
25 30 100

出力例 2

   

300

入出力例 2 において，1 日目には服 2 を，2 日目には服 2 を，3 日目には服 1 を，4 日目には服 2 を，5 日目には服 1 を選ばなければならない．このとき，求める値は |100 - 100| + |100 - 0| + |0 - 100| + |100 - 0| = 300 となる．

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



Sample input:
3 4
31
27
35
20 25 30
23 29 90
21 35 60
28 33 40


Sample output:
80

Submission status: Wrong Answer

Solution code:
d, n = map(int, raw_input().split())
t = [input() for i in range(d)]
a = [map(int, raw_input().split()) for i in range(n)]
dp = [[-1]*n for i in range(d)]
for i in range(n):
    if a[i][0] <= t[0] <= a[i][1]: dp[0][i] = a[i][2]
print dp
for i in range(1,d):
    for j in range(n):
        if a[j][0] <= t[i] <= a[j][1]:
            for k in range(n):
                if dp[i-1][k] >= 0: dp[i][j] = max(dp[i][j], dp[i-1][k] + abs(a[j][2] - a[k][2]))
ans = 0                
for i in range(n):
    if ans < dp[n-1][i]: ans = dp[n-1][i]
print ans

Submission status: Accepted

Solution code:
d, n = map(int, raw_input().split())
t = [input() for i in range(d)]
a = [map(int, raw_input().split()) for i in range(n)]
dp = [[-1]*n for i in range(d)]
for i in range(n):
    if a[i][0] <= t[0] <= a[i][1]: dp[0][i] = 0
for i in range(1,d):
    for j in range(n):
        if a[j][0] <= t[i] <= a[j][1]:
            for k in range(n):
                if dp[i-1][k] >= 0: dp[i][j] = max(dp[i][j], dp[i-1][k] + abs(a[j][2] - a[k][2]))
ans = 0                
for i in range(n):
    ans = max(ans, dp[d-1][i])
print ans

Submission status: Accepted

Solution code:
INF = 10 ** 20
d, n = map(int,input().split())
temp = [int(input()) for i in range(d)]
temp.insert(0,0)
alst = []
blst = []
clst = []
for i in range(n):
  a,b,c = map(int,input().split())
  alst.append(a)
  blst.append(b)
  clst.append(c)

dp = [[0] * n for i in range(d + 1)]

for i in range(n):
  if not (alst[i] <= temp[1] <= blst[i]):
    dp[1][i] = -INF

for i in range(2, d + 1):
  t = temp[i]
  for j in range(n):
    if alst[j] <= t <= blst[j]:
      dp[i][j] = max(dp[i - 1][x] + abs(clst[j] - clst[x]) for x in range(n))

print(max(dp[d]))

Submission status: Accepted

Solution code:
INF = 10 ** 20
def main():
  d, n = map(int,input().split())
  temp = [int(input()) for i in range(d)]
  temp.insert(0,0)
  alst = []
  blst = []
  clst = []
  for i in range(n):
    a,b,c = map(int,input().split())
    alst.append(a)
    blst.append(b)
    clst.append(c)
  
  dp = [[0] * n for i in range(d + 1)]
  
  t1 = temp[1]
  for i in range(n):
    if not (alst[i] <= t1 <= blst[i]):
      dp[1][i] = -INF
  
  for i in range(2, d + 1):
    t = temp[i]
    predp = dp[i - 1]
    for j in range(n):
      cj = clst[j]
      if alst[j] <= t <= blst[j]:
        dp[i][j] = max(predp[x] + (cj - clst[x] if cj >= clst[x] else clst[x] - cj) for x in range(n))
  
  print(max(dp[d]))

main()

Submission status: Accepted

Solution code:
INF = 10 ** 20

def main():
  d, n = map(int,input().split())
  temp = [int(input()) for i in range(d)]
  temp.insert(0,0)
  
  alst = []
  blst = []
  clst = []
  
  for i in range(n):
    a,b,c = map(int,input().split())
    alst.append(a)
    blst.append(b)
    clst.append(c)
  
  dp = [[0] * n for i in range(d + 1)]
  
  t1 = temp[1]
  for i in range(n):
    if not (alst[i] <= t1 <= blst[i]):
      dp[1][i] = -INF
  
  for i in range(2, d + 1):
    t = temp[i]
    predp = dp[i - 1]

    for j in range(n):
      cj = clst[j]
      if alst[j] <= t <= blst[j]:
        save = 0
        for x in range(n):
          cx = clst[x]
          if cj >= cx:
            v = predp[x] + cj - cx
          else:
            v = predp[x] - cj + cx
          if save < v:
            save = v
        dp[i][j] = save

  print(max(dp[d]))

main()

Submission status: Accepted

Solution code:
def getInts():
  return map(int, raw_input().split())

(d, n) = getInts()
t = [input() for i in range(d)]
a = [0 for i in range(n)]
b = [0 for i in range(n)]
c = [0 for i in range(n)]

for i in range(n):
  (a[i], b[i], c[i]) = getInts()

memo = [[-1 for i in range(n)] for j in range(d)]

def solve(day, prev):
  if day == d:
    return 0

  if memo[day][prev] != -1:
    return memo[day][prev]

  ret = 0
  for i in range(n):
    if a[i] <= t[day] and t[day] <= b[i]:
      pt = 0
      if day != 0:
        pt = abs(c[i] - c[prev])
      ret = max(ret, pt + solve(day + 1, i))

  memo[day][prev] = ret
  return ret

print solve(0, 0)

Submission status: Accepted

Solution code:
D,N = map(int,input().split())
T = [ int(input()) for i in range(D) ]
clothes = []
for _ in range(N):
  a,b,c = map(int,input().split())
  clothes.append([a,b,c])

# i日目に服jを来た時の、派手さの絶対値
dp = [ [-1]*(N) for _ in range(D+1) ]
dp[0][0] = 0

for j in range(N):
  a,b,c = clothes[j]
  if a <= T[0] <= b:
    dp[1][j] = c

for i in range(2, D+1):
  for j in range(N):
    a,b,c = clothes[j]
    if a <= T[i-1] <= b:
      for k in range(N):
        if dp[i-1][k] > -1:
          prev_c = clothes[k][2]
          if i > 2:
            dp[i][j] = max(dp[i][j], dp[i-1][k]+abs(prev_c-c))
          else:
            dp[i][j] = max(dp[i][j], abs(prev_c-c))

print(max(dp[-1]))

Submission status: Accepted

Solution code:
D,N = map(int,input().split())

temperature = []
for _ in range(D):
	temperature.append(int(input()))
temperature.insert(0,0)
clothes = []
for _ in range(N):
	a,b,c = map(int,input().split())
	clothes.append([a,b,c])

dp = [[0]*N for i in range(D+1)]
t1 = temperature[1]
for i in range(N):
	if not (clothes[i][0] <= t1 <= clothes[i][1]):
		dp[1][i] = -10**10

for day in range(2,D+1):
	temp = temperature[day]
	pred = dp[day-1]

	for i in range(N):
		ci = clothes[i][2]
		if clothes[i][0] <= temp <= clothes[i][1]:
			max_hadesa = 0
			for j in range(N):
				cj = clothes[j][2]
				if ci >= cj:
					tmp = pred[j]+ci-cj
				else:
					tmp = pred[j]+cj-ci
				if max_hadesa<tmp:
					max_hadesa = tmp
			dp[day][i] = max_hadesa

print(max(dp[D]))

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    D, N = map(int, f_i.readline().split())
    T = tuple(int(f_i.readline()) for i in range(D))
    
    clothes = [tuple(map(int, f_i.readline().split())) for i in range(N)]
    clothes.sort(key=lambda x: x[2])
    
    candidate = []
    for t in T:
        ct = tuple(filter(lambda x: x[0] <= t <= x[1], clothes))
        c_min = ct[0][2]
        c_max = ct[-1][2]
        if c_min == c_max:
            candidate.append((c_min,))
        else:
            candidate.append((c_min, c_max))
    
    dp = [0] * len(candidate[0])
    for c1, c2 in zip(candidate, candidate[1:]):
        dp = [max(rec + abs(ci - cj) for rec, ci in zip(dp, c1)) for cj in c2]
    
    print(max(dp))
    
solve()

Submission status: Accepted

Solution code:
#D
D,N = map(int,input().split())
T = [int(input()) for i in range(D)]
ABC = [list(map(int,input().split())) for i in range(N)]

can = []
for t in T:
    mini = []
    for abc in ABC:
        a,b,c = abc
        if a <= t and t <= b:
            mini.append(c)
    mini.sort()
    can.append([mini[0],mini[-1]])

dp = [[0,0] for i in range(D)]
for i in range(1,D):
    o = can[i-1]
    m = can[i]
    dp[i][0] = max(dp[i-1][0]+abs(o[0]-m[0]),dp[i-1][1]+abs(o[1]-m[0]))
    dp[i][1] = max(dp[i-1][0]+abs(o[0]-m[1]),dp[i-1][1]+abs(o[1]-m[1]))

print(max(dp[D-1]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Hot days
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0579

"""
import sys


def solve(temperatures, clothes):
    points = [[] for _ in range(len(temperatures))]
    for i, t in enumerate(temperatures):
        for c in clothes:
            if c[0] <= t <= c[1]:
                points[i].append(c[-1])
        points[i].sort()

    dp = [[min(points[0]), 0], [max(points[0]), 0]]
    for p in points[1:]:
        dp = [[min(p), max(dp[0][1] + abs(min(p)-dp[0][0]), dp[1][1] + abs(min(p)-dp[1][0]))],
              [max(p), max(dp[0][1] + abs(max(p)-dp[0][0]), dp[1][1] + abs(max(p)-dp[1][0]))]]
    return max(dp[0][1], dp[1][1])


def main(args):
    d, n = map(int, input().split())
    temperatures = [int(input()) for _ in range(d)]
    clothes = [[int(x) for x in input().split()] for _ in range(n)]
    ans = solve(temperatures, clothes)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def run():
  D, N = map(int, input().split())
  d_li = [int(input()) for d in range(D)]
  clothe_li = [list(map(int, input().split())) for n in range(N)]
  dp = [[0]*N for d in range(D)]
  #init
  d = d_li[0]
  for n, (a, b, c) in enumerate(clothe_li):
    if (a <= d) and (d <= b):
      dp[0][n] = 1
  #loop
  for i in range(1, D):
    d = d_li[i]
    #print(dp)
    for pre_n in range(N):
      if dp[i-1][pre_n] == 0: continue
      for n, (a, b, c) in enumerate(clothe_li):
        if (a <= d) and (d <= b):
          #print(c)
          dp[i][n] = max(dp[i][n], 
                         dp[i-1][pre_n] + abs(clothe_li[pre_n][2] - c))
  print(max(dp[-1])-1) 
    
if __name__ == '__main__':
  run()

Submission status: Accepted

Solution code:
d,n=map(int,input().split())
t=[int(input()) for _ in [0]*d]
abc=[list(map(int,input().split())) for _ in [0]*n]

memo=[-1]*101

t_list=[set() for _ in [0]*61]

for a,b,c in abc:
    for j in range(a,b+1):
        t_list[j].add(c)
        
for i in t_list[t[0]]:
    memo[i]=0
    
for i in t[1:]:
    memo2=[-1]*101
    temp=[j for j in t_list[i]]
    for j,k in enumerate(memo):
        if k!=-1:
            for l in temp:
                memo2[l]=max(memo2[l],k+abs(j-l))
    memo=memo2
    
print(max(memo))

Submission status: Accepted

Solution code:
D,N=map(int,input().split())
dp=[[-1]*(N) for i in range(D+1)]
#dp[i][j][k] i日目にｊを着たときの最大
d=[]
for i in range(D):
    i=int(input())
    d.append(i)
J=[]
for j in range(N):
    a,b,c=map(int,input().split())
    J.append([a,b,c])
t=d[0]
h=[-1]*N
for j in range(N):
    a,b,c=J[j]
    if t<a or b<t:
        continue
    h[j]=c
for i in range(2,D+1):
    t=d[i-1]
    for j in range(N):
        a,b,c=J[j]
        if t<a or b<t:
            continue
        for k in range(N):
            if i==2:
                if h[k]==-1:
                    continue
                dp[i][j]=max(abs(J[k][2]-c),dp[i][j])
            if dp[i-1][k]==-1:
                continue
            dp[i][j]=max(dp[i-1][k]+abs(J[k][2]-c),dp[i][j])
ans=0
for i in range(N):
    ans=max(dp[D][i],ans)
print(ans)