TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3889
  • 题目
  • P3889粟粟的书架
    限制 : 时间限制 : - MS   空间限制 : 765536 KB
    评测说明 : 3s
    问题描述

    输入格式

    第一行是三个正整数R, C, M。
    接下来是一个 R行C 列的矩阵,从上到下、从左向右依次给出了每本书的 页数Pi,j。
    接下来 M行,第 i 行给出正整数x1i, y1i, x2i, y2i, Hi,表示第i 天的指定区域 是﹙x1i, y1i﹚与﹙x2i, y2i﹚间的矩形,总页数之和要求不低于 Hi。
    保证 1≤x1i≤x2i≤R,1≤y1i≤y2i≤C。

    输出格式

    有M行,第i 行回答粟粟在第 i 天时为摘到苹果至少需要 拿取多少本书。
    如果即使取走所有书都无法摘到苹果,则在该行输出“Poor QLW” (不含引号)。

    样例输入 1

    5 5 7
    14 15 9 26 53 
    58 9 7 9 32 
    38 46 26 43 38
    32 7 9 50 28 
    8 41 9 7 17 
    1 2 5 3 139 
    3 1 5 5 399 
    3 3 4 5 91 
    4 1 4 1 33 
    1 3 5 4 185 
    3 3 4 3 23 
    3 1 3 3 108 

    样例输出 1

    6
    15 

    Poor QLW 



    样例输入 2

    1 10 7 
    14 15 9 26 53 58 9 7 9 32 
    1 2 1 9 170 
    1 2 1 9 171 
    1 5 1 7 115 
    1 1 1 10 228 
    1 4 1 4 4570457
    1 1 1 1 11
    1 7 1 8 16

    样例输出 2

    6


    10 
    Poor QLW 


    提示

    对于 10%的数据,满足 R, C≤10; 
    对于 20%的数据,满足 R, C≤40; 
    对于 50%的数据,满足 R, C≤200,M≤200,000; 
    另有 50%的数据,满足 R=1,C≤500,000,M≤20,000; 
    对于 100%的数据,满足 1≤Pi,j≤1,000,1≤Hi≤2,000,000,000。


    来源  sdoi 2010