CF1060C Maximum Subrectangle

    • 153通过
    • 228提交
  • 题目来源 CodeForces 1060C
  • 评测方式 RemoteJudge
  • 标签 前缀和 枚举,暴力
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    现在给出一个长度为$N$的$a$数列,一个长度为$M$的$b$数列. 现在需要构造出一个矩阵$c$,其中$c_{i,j}=a_i \times b_j$.再给出一个$x$,请在矩阵中找出一个最大的矩形,使得这个矩形中的所有值的和小于等于$x$.

    题目描述

    You are given two arrays $ a $ and $ b $ of positive integers, with length $ n $ and $ m $ respectively.

    Let $ c $ be an $ n \times m $ matrix, where $ c_{i,j} = a_i \cdot b_j $ .

    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.

    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}^{x2}{\sum{j=y_1}^{y2}{c{i,j}}} \leq x. $ $$

    输入输出格式

    输入格式:

    The first line contains two integers $ n $ and $ m $ ( $ 1 \leq n, m \leq 2000 $ ).

    The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 2000 $ ).

    The third line contains $ m $ integers $ b_1, b_2, \ldots, b_m $ ( $ 1 \leq b_i \leq 2000 $ ).

    The fourth line contains a single integer $ x $ ( $ 1 \leq x \leq 2 \cdot 10^{9} $ ).

    输出格式:

    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 $ .

    输入输出样例

    输入样例#1: 复制
    3 3
    1 2 3
    1 2 3
    9
    
    输出样例#1: 复制
    4
    
    输入样例#2: 复制
    5 1
    5 4 2 4 5
    2
    5
    
    输出样例#2: 复制
    1
    

    说明

    Matrix from the first sample and the chosen subrectangle (of blue color):

    Matrix from the second sample and the chosen subrectangle (of blue color):

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。