Pagini recente » Cod sursa (job #3241357) | Cod sursa (job #570440) | Cod sursa (job #2239552) | Cod sursa (job #3221099) | Cod sursa (job #70561)
Cod sursa(job #70561)
#include<stdio.h>
#define Nmax 305
/*
int calc(long long X)
{
int i,j,p,q,li,lf;
//linii limita
for(p=1;p<=2*M;p++)
for(q=p+R-1; q<=p+M-1 && q<=2*M; q++)
{
//deque
B[0]=0;
for(j=1;j<=2*N;j++)
B[j]= COL[q][j] - COL[p-1][j] - X*(q-p+1) + B[j-1];
//intre limitele C si N
li=lf=1;
dq[1]=0;
for(i=C;i<=2*N;i++)
{
if(B[i] - B[dq[li]] >= 0)
return 1;
if(i-dq[li] == N) li++;
j= i-C+1;
while(li<=lf && B[dq[lf]] > B[j]) lf--;
dq[++lf]=j;
}
}
return -1;
}
*/
int main()
{
FILE *fin=fopen("balans.in","r"),
*fout=fopen("balans.out","w");
int i,j;
int COL[Nmax][Nmax],B[Nmax];
int M,N,R,C,dq[Nmax];
int A[Nmax][Nmax];
long long CST=1000;
fscanf(fin,"%d%d%d%d\n",&M,&N,&R,&C);
for(i=1;i<=M;++i)
for(j=1;j<=N;++j)
{
fscanf(fin,"%d",&A[i][j]);
A[i+M][j]= A[i+M][j+N] = A[i][j+N]= A[i][j];
}
//sume partiale
for(i=1;i<=2*M;++i)
for(j=1;j<=2*N;++j)
COL[i][j]= COL[i-1][j] + A[i][j];
int li=0,lf=100000000,mij,sol=0,val;
long long p,q,X;
int st,dr;
while(li<=lf)
{
mij=(li+lf)>>1;
X=(long long)mij;
//functia
val=-1;
for(p=1;p<=2*M && val<0;++p)
for(q=p+R-1; q<=p+M-1 && q<=2*M && val<0;++q)
{
//deque
B[0]=0;
for(j=1;j<=2*N;++j)
B[j]= CST*(COL[q][j] - COL[p-1][j]) - X*(q-p+1) + B[j-1];
//intre limitele C si N
st=dr=1;
dq[1]=0;
for(i=C;i<=2*N;++i)
{
if(B[i] - B[dq[st]] >= 0)
val=1;
if(i-dq[st] == N) ++st;
j= i-C+1;
while(st<=dr && B[dq[dr]] > B[j]) --dr;
dq[++dr]=j;
}
}
//
if( val < 0 )
lf=mij-1;
else
{
li=mij+1;
sol=mij;
}
}
fprintf(fout,"%d.%03d\n",sol/1000,sol%1000);
fclose(fin);
fclose(fout);
return 0;
}