제출 #252013

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
252013		zecookiez	걷기 (NOI12_walking)	Pypy 2	25 / 25	39 ms	6360 KiB

walking

from sys import stdin
input = stdin.readline

L, N = map(int, input().split())
arr = [map(int, input().split()) for i in xrange(N)]

arr.sort()
brr = [float(L) / j + i for i, j in arr][::-1]

# count LIS

def lis(n, arr, output = False):
    d = [0] * (n + 1)
    p = [0] * (n + 1)
    L = 0
    for i in xrange(n):
        low = 1
        high = L
        while low <= high:
            mid = (low + high) / 2
            if arr[d[mid]] < arr[i]: low = mid + 1
            else: high = mid - 1
        p[i] = d[low - 1]
        d[low] = i
        L = max(L, low)
    print L
    if output:
        ans = []
        k = d[L]
        for i in xrange(L):
            ans.append(arr[k])
            k = p[k]
        print " ".join(map(str, ans[::-1]))

lis(N, brr)

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 5 / 5
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7