Problem:


Movie

Problem

太郎君は夏休みの間、毎日１つの映画を近所の映画館で見ることにしました。
（太郎君の夏休みは8月1日から8月31日までの31日間あります。）

その映画館では、夏休みの間にn つの映画が上映されることになっています。
それぞれの映画には 1 から n までの番号が割り当てられており、i 番目の映画は8月 ai 日から8月 bi 日の間だけ上映されます。

  

太郎君は映画を見た時、それが初めて見る映画だった場合は 100 の幸福度を得ることができます。
しかし、過去に 1 度でも見たことのある映画だった場合は 50 の幸福度を得ます。

太郎君は上映される映画の予定表をもとに、夏休みの計画を立てることにしました。
太郎君が得られる幸福度の合計値が最大になるように映画を見たときの合計値を求めてください。

どの日も必ず1つ以上の映画が上映されていることが保証されます。

  

Input

入力は以下の形式で与えられる。

n
a1 b1
a2 b2
...
an bn

1行目に、1つの整数 n が与えられる。
2行目からの n 行のうち i 行目には 2 つの整数 ai, bi  が空白区切りで与えられる。

Constraints

1 ≤ n ≤ 100

1 ≤ ai ≤ bi ≤ 31 (1 ≤ i ≤ n)

Output

太郎君の得られる幸福度の合計値の最大値を出力せよ。

Sample Input 1

4
1 31
2 2
2 3
3 3

Sample Output 1

1700

Sample Input 2

5
1 10
10 20
20 21
22 31
4 20

Sample Output 2

1800



Sample input:
4
1 31
2 2
2 3
3 3


Sample output:
1700

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())
As = []
Bs = []
movies = [[] for x in range(31)]
for n in range(N):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    As.append(a)
    Bs.append(b)
    for day in range(a, b+1):
        movies[day].append(n)
print(movies)

picked = [False] * N
ans = 0
for day in range(31):
    # ????????????????????????
    unseen_movies = [m for m in movies[day] if not picked[m]]

    # ???????????????????????????
    if len(unseen_movies) == 0:
        ans += 50
    else:
        # ????????????????????????????????????????????£??¨????????????????????????????????????
        lastday = 1000
        should_see = -1
        for m in unseen_movies:
            if Bs[m] < lastday:
                lastday = Bs[m]
                should_see = m
        picked[should_see] = True
        ans += 100
print(ans)

Submission status: Accepted

Solution code:
# AOJ 1566 Movie
# Python3 2018.7.13 bal4u

n = int(input())
tbl = []
for i in range(n):
	a, b = map(int, input().split())
	tbl.append([b, a])
tbl.sort()
ans = saw = 0
seen = [0]*101
for i in range(1, 32):
	for j in range(n):
		if i < tbl[j][1] or tbl[j][0] < i: continue
		if seen[j]: continue
		ans += 100; seen[j] = 1; saw += 1
		break;
print(ans+(31-saw)*50)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())
As = []
Bs = []
movies = [[] for x in range(31)]
for n in range(N):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    As.append(a)
    Bs.append(b)
    for day in range(a, b+1):
        movies[day].append(n)

picked = [False] * N
ans = 0
for day in range(31):
    # ????????????????????????
    unseen_movies = [m for m in movies[day] if not picked[m]]

    # ???????????????????????????
    if len(unseen_movies) == 0:
        ans += 50
    else:
        # ????????????????????????????????????????????£??¨????????????????????????????????????
        lastday = 1000
        should_see = -1
        for m in unseen_movies:
            if Bs[m] < lastday:
                lastday = Bs[m]
                should_see = m
        picked[should_see] = True
        ans += 100
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import heapq
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n = II()
M = [LI() for _ in range(n)]
for a in zip(* M):
    start = set(a)
    break
M.sort()
# print(start)

ans = 0
index = 0
hq = []
for i in range(31):
    if i + 1 in start:
        while i + 1 in start and M[index][0] == i + 1:
            heapq.heappush(hq, M[index][1])
            index += 1
            if index >= n:
                break

    while hq and hq[0] < i + 1:
        if hq:
            tmp = heapq.heappop(hq)
        else:
            break

    if hq:
        ans += 100
        tmp = heapq.heappop(hq)
    else:
        ans += 50

    # print(i+1, ans, hq)

print(ans)

Submission status: Runtime Error

Solution code:
# AOJ 1566 Movie
# Python3 2018.7.13 bal4u

n = int(input())
tbl = []
for i in range(n):
	a, b = map(int, input().split())
	tbl.append([b, a])
tbl.sort()
ans = saw = 0
seen = [0]*32
for i in range(1, 32):
	for j in range(n):
		if i < tbl[j][1] or tbl[j][0] < i: continue
		if seen[j]: continue
		ans += 100; seen[j] = 1; saw += 1
		break;
print(ans+(31-saw)*50)