You have been given a matrix C _N*M, each element E of C _N*M is positive and no more than 1000, The problem is that if there exist N numbers a1, a2, … an and M numbers b1, b2, …, bm, which satisfies that each elements in row-i multiplied with ai and each elements in column-j divided by bj, after this operation every element in this matrix is between L and U, L indicates the lowerbound and U indicates the upperbound of these elements.

3 3 1 6

2 3 4

8 2 6

5 2 9

YES
 

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

const double inf=0x7fffffff;

int Laxt[maxn],Next[maxn<<],To[maxn<<];

int vis[maxn],inq[maxn],cnt,n,m;

double dis[maxn],Len[maxn<<];

void update()

{

    cnt=;

    memset(Laxt,,sizeof(Laxt));

    memset(vis,,sizeof(vis));

    memset(inq,,sizeof(inq));

}

void add(int u,int v,double d)

{

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt;

    To[cnt]=v;

    Len[cnt]=d;

}

bool spfa()

{

    int times=;

    for(int i=;i<=n+m;i++)  dis[i]=-inf;

    queue<int>q;

    q.push(); dis[]=; inq[]=;

    while(!q.empty()){

        if(times>*(n+m)) return false;

        int u=q.front(); q.pop(); inq[u]=;

        for(int i=Laxt[u];i;i=Next[i]){

            int v=To[i];

            if(dis[v]<dis[u]+Len[i]){

                dis[v]=dis[u]+Len[i];

                if(!inq[v]){

                   inq[v]=; vis[v]++; q.push(v); times++;

                   if(vis[v]>sqrt(n+m)) return false;

                }

            }

        }

    } return true;

}

int main()

{

    int i,j; double x,L,U;

    while(~scanf("%d%d%lf%lf",&n,&m,&L,&U)){

        update();

        L=log10(L);U=log10(U);

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

         for(j=;j<=m;j++){

            scanf("%lf",&x);

            add(n+j,i,L-log10(x));

            add(i,n+j,-U+log10(x));

        }

        for(i=;i<=n+m;i++) add(,i,);

        if(spfa()) printf("YES\n");

        else printf("NO\n");

    } return ;

}

//1，知道要去对数；2，判定时的投机取巧。