PKU 2078 Matrix

http://poj.org/problem?id=2078
行列の行を好きなだけシフトしていい時に、与えられた式の答えを求める。

1行目は変更しなくていいことに気づかなくて、O(n^(n+2))をO(n^(n+1))のオーダーにしないとTLEした。
入力がcinとかだったらまだ間に合わないかもしれない。
多分これは頭悪い方の解法な気がする。

int ret;
char c;
bool m;
int in(){
  ret=0;
  m=0;
  while(!isdigit(c=getchar()) && c!='-');
  if(c=='-')m=1;
  else ret=c-'0';

  while(isdigit(c=getchar()))ret=(ret<<3)+(ret<<1)+c-'0';
  if(m)return -ret;
  return ret;
}

int mat[10][10];
int ac[7];
int n;
int ans;

void dfs(int ne){
  if(ne==0){
    int c=0;
    rep(i,n){
      int sum=0;
      rep(j,n)sum+=mat[j][(i+ac[j])%n];
      c=max(c,sum);
    }
    ans=min(c,ans);
    return;
  }

  rep(i,n){
    ac[ne-1]=i;
    dfs(ne-1);
  }
}

main(){
  while(n=in(),~n){
    rep(i,n)rep(j,n)mat[i][j]=in();
    ans=1<<28;
    dfs(n-1);
    printf("%d\n",ans);
  }
}