All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Maximum Area
Tag(s):

Algorithms, Graph, Medium, Shortest path problem

Problem
Editorial
Analytics

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.

 

SAMPLE INPUT
3 18
4 7 11
7 100 100
100 100 100
SAMPLE OUTPUT
4
Explanation

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HourStorm #11

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?