All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Maximum Area

Algorithms, Graph, Shortest path problem


While walking around Hackerland, Marichka found a large square grid of size \(N\cdot N\) consisting of unit squares of size \(1\cdot1\). Now Marichka wants to explore it as much as possible.

In one move Marichka can move to the cell which shares an edge with cell, where Marichka currently is. It will take her \(a_{ij}\) (\(1 \le a_{ij} \le 10^{6}\)) minutes, where \((i,j)\) is the coordinates of the cell where Marichka moved. Marichka defines her exploration level as the maximum row number for all cells she visited multiplied by maximum column number for all cells she visited. Marichka always starts her exploration in the cell with coordinates \((1,1)\). Your task is to help Marichka maximize this score. Marichka is limited in time, so she can't spend more than \(T\) minutes exploring the grid.

Input format

The first line contains two integers \(N, T\) (\(1 \le N \le 150, 1 \le T \le 10^{9}\)) --- size of the grid.
Each line \(i\) of the \(N\) subsequent lines (where \(1 \le i \le N\)) contains \(N\) integers describing \(i\)-th row of the grid --- \(a_{i1}, a_{i2}, ..., a_{in}\).

Output format

Output maximum Marichka's exploration level.


3 18
4 7 11
7 100 100
100 100 100

Marichka can move to the cell (1,2) in time 7, then to the cell (1,1) in time 4, then to the cell (2,1) in time 7. The maximum column number will be 2, the maximum row number will be 2, so answer in such case will be \(2\cdot2 = 4\)

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications