P2219 [HAOI2007]修筑绿化带

    • 33通过
    • 102提交
  • 题目提供者xmyzwls 管理员
  • 标签 单调队列 平衡树 队列 各省省选 2007 河南 高性能
  • 难度 提高+/省选-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    为了增添公园的景致,现在需要在公园中修筑一个花坛,同时在画坛四周修建一片绿化带,让花坛被绿化带围起来。

    如果把公园看成一个M*N的矩形,那么花坛可以看成一个C*D的矩形,绿化带和花坛一起可以看成一个A*B的矩形。

    如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和,那么,

    绿化带的肥沃度=A*B块的肥沃度-C*D块的肥沃度

    为了使得绿化带的生长得旺盛,我们希望绿化带的肥沃度最大。

    输入输出格式

    输入格式:

    第一行有6个正整数M,N,A,B,C,D

    接下来一个M*N的数字矩阵,其中矩阵的第i行j列元素为一个整数Xij,表示该花园的第i行第j列的土地“肥沃度”。

    输出格式:

    一个正整数,表示绿化带的最大肥沃程度。

    输入输出样例

    输入样例#1: 复制
    4 5 4 4 2 2
    20 19 18 17 16
    15 14 13 12 11
    10 9 8 7 6
    5 4 3 2 1
    
    输出样例#1: 复制
    132

    说明

    数据范围

    30%的数据,1<=M,N<=50

    100%的数据,1<=M,N<=1000,1<=A<=M,1<=B<=N,1<=C<=A-2,1<=D<=B-2,1<=“肥沃度”<=100

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