codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1060C.md (1953B)


      1 Source: https://codeforces.com/problemset/problem/1060/C
      2 
      3 C. Maximum Subrectangle
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given two arrays $a$ and $b$ of positive integers, with length $n$ and $m$ respectively.
     22 
     23 Let $c$ be an $n \times m$ matrix, where $c_{i,j} = a_i \cdot b_j$.
     24 
     25 You need to find a subrectangle of the matrix $c$ such that the sum of its elements is at most $x$, and its area (the total number of elements) is the largest possible.
     26 
     27 Formally, you need to find the largest number $s$ such that it is possible to choose integers $x_1, x_2, y_1, y_2$ subject to $1 \leq x_1 \leq x_2 \leq n$, $1 \leq y_1 \leq y_2 \leq m$, $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1) = s$, and $$\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x.$$
     28 
     29 Input
     30 
     31 The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 2000$).
     32 
     33 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 2000$).
     34 
     35 The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \leq b_i \leq 2000$).
     36 
     37 The fourth line contains a single integer $x$ ($1 \leq x \leq 2 \cdot 10^{9}$).
     38 
     39 Output
     40 
     41 If it is possible to choose four integers $x_1, x_2, y_1, y_2$ such that $1 \leq x_1 \leq x_2 \leq n$, $1 \leq y_1 \leq y_2 \leq m$, and $\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x$, output the largest value of $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$ among all such quadruplets, otherwise output $0$.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 3 3  
     49 1 2 3  
     50 1 2 3  
     51 9
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 4
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 5 1  
     64 5 4 2 4 5  
     65 2  
     66 5
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 1
     73 ```
     74 
     75 Note
     76 
     77 Matrix from the first sample and the chosen subrectangle (of blue color):
     78 
     79  ![](https://espresso.codeforces.com/7ee36e48738084e46c7eb3f4e2d7b876f55e11a0.png) 
     80 
     81 Matrix from the second sample and the chosen subrectangle (of blue color):
     82 
     83  ![](https://espresso.codeforces.com/17d730bbfb7ec3c0ed314dffd147088702cb1376.png)