Farmer John has an apple farm. As the harvesting season approaches, he is planning for harvesting the apples. The farm is formed as a rectangular grid with N rows and M columns. Each grid cell may have an apple tree in it.
Farmer John will start at the top-left cell of the farm, and drive a cultivator to collect the apples. Unfortunately, the cultivator is quite old and has some problems - for one thing, it can only move in two directions: down and right. In other words, if the cultivator is located at (i, j), it can either go to (i + 1, j) or (i, j + 1).
FJ wants a single trip on his cultivator which can collect the most apples possible. Write a program to find a path with maximum apple trees.
Your program is to read from standard input. The input consists of T test cases. The number of test cases T (1 <= T <= 100) is given in the first line of the input. In the first line of each case, 3 integers N,M,K(1 <= N,M <= 2147483647, 1 <= K <= 20000) will be given.In the next K lines, the location of each apple tree yi, xi will be given (1 <= yi <= N, 1 <= xi <= M). You can assume no cell contains more than one tree.
Your program is to write to standard output. Print exactly one line for each test case, containing the maximum number of apple trees Farmer John can visit.
2 3 3 2 1 1 3 3 5 5 10 1 1 1 2 1 3 1 4 1 5 2 1 2 5 3 5 4 5 5 5
O(k2) 보다 빠른 알고리즘이 있나요? Java에서는 시간초과 걸리네요.
5년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.