Submission #632886

#	Time	Username	Problem	Language	Result	Execution time	Memory
632886		beaconmc	Global Warming (CEOI18_glo)	Pypy 3	17 / 100	250 ms	43764 KiB

glo

def bisect(arr, v, asc):
    lo = 0
    hi = len(arr)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if asc:
            if v <= arr[mid]:
                hi = mid
            else:
                lo = mid + 1
        else:
            if v >= arr[mid]:
                hi = mid
            else:
                lo = mid + 1

    return lo

def find_lis(inp):
    lis_ending = [0] * len(inp)
    lis_ending_arr = []
    
    lis_starting = [0] * len(inp)
    lis_starting_arr = []

    for i in range(len(inp)):
        # LIS ending at i
        idx = bisect(lis_ending_arr, inp[i], True)
        if idx == len(lis_ending_arr):
            lis_ending_arr.append(inp[i])
        else:
            lis_ending_arr[idx] = inp[i]

        lis_ending[i] = len(lis_ending_arr)

        # LIS starting at i
        j = len(inp) - 1 - i
        idx = bisect(lis_starting_arr, inp[j], False)
        
        if idx == len(lis_starting_arr):
            lis_starting_arr.append(inp[j])
        else:
            lis_starting_arr[idx] = inp[j]

        lis_starting[j] = len(lis_starting_arr)

    return lis_ending, lis_starting

def beacon(inp):
    lis_ending, lis_starting = find_lis(inp)
    res = 0

    for i in range(len(inp) - 1):
        val = lis_ending[i] + lis_starting[i + 1]
        res = max(res, val)

    res = max(res, lis_ending[len(inp) - 1])
    return res

n,x = map(int, input().split())
inp = [int(x) for x in input().split()]
print(beacon(inp))

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25