PKU 2442 Sequence

http://poj.org/problem?id=2442
n個の数字を含む集合がm個与えられる。
このとき、各集合から１つずつ数字を取り出したとてn個の数字の集合を作るときn^m通りの集合が作れる。
この集合に含まれる数字の和として考えられるもののうち小さいものからn個を出力しろというような問題。

愚直にやるとMLEしたので、配列を削減してTLE。
仕方ないので、小さい方から数えて和がnを超えたら打ち切るようにして何とかおさまりました。

int dp[2][2000000];

int in[100][2000];

main(){
  int T;
  scanf("%d",&T);
  while(T--){
    int m,n;
    scanf("%d%d",&m,&n);
    rep(i,m)rep(j,n)scanf("%d",in[i]+j);

    memset(dp,0,sizeof(dp));

    rep(i,n)++dp[0][in[0][i]];

    for(int i=1;i<m;++i){
      memset(dp[i&1],0,sizeof(dp[i&1]));
      rep(j,n){
        int tn=0;
        for(int k=in[i][j];k<=1000000;++k){
          dp[i&1][k]+=dp[i-1&1][k-in[i][j]];
          tn+=dp[i&1][k];
          if(tn>n)break;
        }
      }
    }
    int out=0;
    int idx=0;
    while(out<n){
      if(dp[m-1&1][idx]){
        printf("%d ",idx);
        ++out;
        --dp[m-1&1][idx];
      }else ++idx;
    }
    printf("\n");
  }
}