TIOJ 1062 用餐地點(Lunch) ( 95北市賽 prob 4 )

poao899    -8K    121MS    G++    0.74K     2009-11-11 11:02:41                                                 .



測資<100

但是可以O(n^2)


被阿思學長捏到QQ














"如果改變輸入格式可以O(n)..."













//*************************


//95 prob 4

#include<stdio.h>
int nSum[100],mSum[100];
int dpN[100],dpM[100];
int n,m,t,minN,minM,nn,mm;
main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            scanf("%d",&t);
            nSum[i]+=t;
            mSum[j]+=t;
        }
    for(int i=0;i<n;i++)
        dpN[0]+=nSum[i]*i;
    for(int i=1;i<n;i++)
        nSum[i]+=nSum[i-1];
    minN=dpN[0];nn=0;
    for(int i=1;i<n;i++){
        (dpN[i]=dpN[i-1]-nSum[n-1]+nSum[i-1]*2);
        if(minN>dpN[i]){
            minN=dpN[i];
            nn=i;
        }
    }
    for(int i=0;i<m;i++)
        dpM[0]+=mSum[i]*i;
    for(int i=1;i<m;i++)
        mSum[i]+=mSum[i-1];
    minM=dpM[0];mm=0;
    for(int i=1;i<m;i++){
        (dpM[i]=dpM[i-1]-mSum[m-1]+mSum[i-1]*2);
        if(minM>dpM[i]){
            minM=dpM[i];
            mm=i;
        }
    }
    printf("%d %d\n",nn+1,mm+1);
}