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  80 81 Matrix from the second sample and the chosen subrectangle (of blue color): 82 83 