bzoj1127: [POI2008]KUP

Description

给一个n*n的地图，每个格子有一个价格，找一个矩形区域，使其价格总和位于[k,2k]

Input

输入k n（n<2000)和一个n*n的地图

Output

输出矩形的左上和右下的列-行坐标或NIE

Sample Input

inputdata1
4 3
1 1 1
1 9 1
1 1 1
inputdata2
8 4
1 2 1 3
25 1 2 1
4 20 3 3
3 30 12 2

Sample Output

outputdata1
NIE
outputdata2
2 1 4 2

题解：

http://blog.csdn.net/popoqqq/article/details/44625423

code：

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long int64;

 char ch;

 bool ok;

 void read(int &x){

     for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;

     for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());

     if (ok) x=-x;

 }

 const int maxn=;

 int k,n,a[maxn][maxn],head,tail,last,h[maxn],top,l[maxn],r[maxn];

 int64 sum[maxn][maxn];

 int64 calc(int x,int y,int xx,int yy){return sum[xx][yy]-sum[xx][y-]-sum[x-][yy]+sum[x-][y-];}

 struct Data{

     int val,id;

 }que[maxn],stack[maxn];

 void output(int x,int y,int xx,int yy){

     while (calc(x,y,xx,yy)>k*){

         if (x==xx) y++;

         else if (calc(x+,y,xx,yy)>=k) x++;

         else xx--;

     }

     printf("%d %d %d %d\n",y,x,yy,xx);

     exit();

 }

 void work(int x){

     /*head=1,tail=0,last=1;

     for (int i=1;i<=n;i++){

         while (head<=tail&&que[tail].val>=h[i]) tail--;

         que[++tail]=(Data){h[i],i};

         while (head<=tail&&que[head].val==0) last=que[head++].id+1;

         if (head<=tail&&calc(x-que[head].val+1,last,x,i)>=k) output(x-que[head].val+1,last,x,i);

     }*/

     top=;

     for (int i=;i<=n+;i++){

         while (top&&stack[top].val>h[i]) r[stack[top--].id]=i-;

         stack[++top]=(Data){h[i],i};

     }

     top=;

     for (int i=n;i>=;i--){

         while (top&&stack[top].val>h[i]) l[stack[top--].id]=i+;

         stack[++top]=(Data){h[i],i};

     }

     for (int i=;i<=n;i++)

         if (h[i]) if (calc(x-h[i]+,l[i],x,r[i])>=k) output(x-h[i]+,l[i],x,r[i]);

 }

 int main(){

     read(k),read(n);

     for (int i=;i<=n;i++) for (int j=;j<=n;j++){

         read(a[i][j]),sum[i][j]=sum[i][j-]+a[i][j];

         if (k<=a[i][j]&&a[i][j]<=k*){printf("%d %d %d %d\n",j,i,j,i);return ;}

     }

     for (int i=;i<=n;i++) for (int j=;j<=n;j++) sum[i][j]+=sum[i-][j];

     for (int i=;i<=n;i++){

         for (int j=;j<=n;j++) h[j]=a[i][j]>k*?:h[j]+;

         work(i);

     }

     puts("NIE");

     return ;

 }