Submission #252013

#	Time	Username	Problem	Language	Result	Execution time	Memory
252013		zecookiez	Walking (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