oj.uz

Submission #252013

# Submission time Handle Problem Language Result Execution time Memory
252013 2020-07-23T15:57:19 Z zecookiez Walking (NOI12_walking) PyPy
25 / 25
 39 ms 6360 KB 
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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5088 KB Output is correct
2 Correct 22 ms 4960 KB Output is correct
3 Correct 26 ms 4960 KB Output is correct
4 Correct 23 ms 4960 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4960 KB Output is correct
2 Correct 31 ms 4952 KB Output is correct
3 Correct 33 ms 4960 KB Output is correct
4 Correct 23 ms 4952 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4960 KB Output is correct
2 Correct 25 ms 4952 KB Output is correct
3 Correct 24 ms 4960 KB Output is correct
4 Correct 25 ms 4960 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6360 KB Output is correct
2 Correct 35 ms 5856 KB Output is correct
3 Correct 31 ms 5592 KB Output is correct
4 Correct 28 ms 5212 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5208 KB Output is correct
2 Correct 32 ms 5256 KB Output is correct
3 Correct 33 ms 5336 KB Output is correct
4 Correct 32 ms 5088 KB Output is correct