COCI 2008/2009, Contest #1

Task SKAKAVAC

A grasshopper is in a flower field. The field contains N·N flowers arranged in N rows and N columns. For each flower in the field, we know how many petals it has.

The grasshopper is initially on the flower in row R and column C. Its goal is to visit as many flowers as possible while obeying these rules:

  1. It can only jump into an adjacent row or column. If it jumps into the adjacent row, it must jump at least two columns, and if it jumps into the adjacent column, it must jump at least two rows.
    In other words, it can jump from flower (r1, c1) to flower (r2, c2) if:
    • |r1 - r2| = 1 and |c1 - c2| > 1 or
    • |c1 - c2| = 1 and |r1 - r2| > 1
  2. The number of petals on the next flower must be strictly larger than the number of petals on the previous flower.
Write a program that calculates the largest number of flowers the grasshopper can visit.

Input

The first line contains the integer N (1 ≤ N ≤ 1500), the size of the field.
The second line contains integers R (1 ≤ R ≤ N) and C (1 ≤ C ≤ N), the grasshopper's initial position.
The next N lines contain N positive integers separated by spaces, each less than 1 000 000, the numbers of petals on the flowers.

Output

Output a single integer—the largest number of flowers the grasshopper can visit.

Grading

In test data worth 50% of points, N will be at most 100.
In test data worth 80% of points, N will be at most 1000.

Examples

Input

4
1 1
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

Output

4

Input

5
3 3
20 16 25 17 12
11 13 13 30 17
15 29 10 26 11
27 19 14 24 22
23 21 28 18 13

Output

21

All Submissions
Best Solutions


Point Value: 30 (partial)
Time Limit: 10.00s
Memory Limit: 35M
Added: Oct 18, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Are tests from hsin.hr? I tested my program on last test and it passes on my computer, but here it gets RE. Could you help me?

You're getting SIGABRTs, which probably indicates you're exceeding the memory limit on an STL allocation. I checked your submission and confirmed this is the case.

This information is listed in the README.

This problem seems to require specialized datastructures( or at least a trick, or is a very hard D.P ) as I just found out that when N <= 100, it requires almost a second. My solution is poor ( it seems to be exponential ).

What did the people who solved it use ? Or the observations they made ?

If you mean you think it requires knowledge of some pro data structure that most noobs wouldn't understand (like a Fibonacci heap), then no, it doesn't.

Okay I am a noob. Please could anyone tell me what am I doing wrong ?

You are currently using recursion, which is too slow.
Find another way that only processes each location on the grid once.

I still don't get it, is my recurrence wrong ? If this is a dp, then a greedy choice doesn't help, right ?

in COCI 08-09's PDF it's 35M!!!!

Okay, it's been increased to 35M.

....thanks and i got ac by decrease array counts..