가톨릭대는 고양이를 사랑해

• 격자 경로에서 가장 많은 점수를 얻는 이동 경로를 찾는 문제이다.
• 링크에서 설명한대로 가장 긴 증가하는 부분 수열 (LIS; Longest Increasing Subsequence)를 이용해서 O(klogk)에 풀 수 있다.
• 가톨릭대 밖에 고양이가 존재할수 있다는 조건은 왜 굳이 넣어서 그냥 쓸데없이 귀찮게 만들었는지는 모르겠다…

"""Solution code for "BOJ 23035. 가톨릭대는 고양이를 사랑해".

- Problem link: https://www.acmicpc.net/problem/23035
- Solution link: http://www.teferi.net/ps/problems/boj/23035

Tags: [LIS]
"""

import sys
from teflib import seqtask


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    T = int(sys.stdin.readline())
    poses = []
    for _ in range(T):
        r_i, c_i = [int(x) - 1 for x in sys.stdin.readline().split()]
        if r_i < N and c_i < M:
            poses.append((r_i, c_i))

    seq = [c for r, c in sorted(poses)]
    answer = seqtask.longest_inc_subseq_length(seq, strict=False)

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.longest_inc_subseq_length