P3474 [POI2008]KUP-Plot purchase

    • 73通过
    • 261提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 单调队列 贪心 POI 2008 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Byteasar is going to buy an industrial plot.

    His fortune is estimated at bythalers and this is exactly the amount Byteasar would like to spend on the parcel.

    Finding a parcel worth exactly bythalers, however, is not an easy task.

    For this reason Byteasar is ready to buy a more expensive plot.

    He considers taking out a loan. The Byteotian Credit Bank will grant him a loan of up to bythalers. Thus, Byteasar can spend no more than bythalers on the parcel and he would like to spend no less than bythalers.

    The area in which Byteasar wants to buy his parcel is a square with side length of metres.

    The current landlords have set up various prices per square metre.

    Byteasar has spoken to each one of them and has then prepared a price map of the area.

    The map depicts the price of every metre by metre square. Clearly, there are such squares.

    Now is the time to find the dream parcel.

    It has to be rectangular and consist of whole unit squares.

    Byteasar has already started looking for the plot on the map, but after many hours he was still unable to find a suitable one.

    Be a chap and help him!

    Task Write a programme that:

    reads the numbers and from the standard input, along with the price map of the area, determines a parcel with price in the interval or states that no such parcel exists, writes out the result to the standard output.

    给定k,n,和n*n的矩阵,求一个子矩形满足权值和在[k,2k]之间

    感谢@cn:苏卿念 提供的spj

    输入输出格式

    输入格式:

    The first line of the standard input contains two integers, and , separated by a single space, , .

    Each of the following lines contains non-negative integers, separated by single spaces.

    number in the line no. denotes the price of unit square with coordinates .

    The price of one square metre does not exceed bythalers.

    输出格式:

    If no plot with price in the interval exists, your programme should output exactly one line with word NIE (NO in Polish).

    Otherwise it should print out one line with four positive integers separated by single spaces and denoting the rectangle's coordinates.

    denotes the upper left rectangle corner, while the lower right corner.

      Then it consists of the squares:
    
      ![](http://main.edu.pl/images/OI15/kup-en-tex.25.png).
    
      The sum ![](http://main.edu.pl/images/OI15/kup-en-tex.26.png) of prices of the squares forming up this rectangle should      satisfy the inequality ![](http://main.edu.pl/images/OI15/kup-en-tex.27.png).

    If more than one rectangular parcel satisfies this condition, pick one arbitrarily.

    输入输出样例

    输入样例#1: 复制
    8 4
    1 2 1 3
    25 1 2 1
    4 20 3 3
    3 30 12 2
    输出样例#1: 复制
    2 1 4 2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。