結果

提出番号	1866
提出者	popo
言語	C++
提出日時	2018-08-04 14:16:33
問題名	(72)K-th DigitSum
結果	MLE
点数	0%

---

テストケース

ソースコード

#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;

struct X{
  int id,su,di;
  X(){di=-1;}
  X(int a,int c,int d){
    id=a;

    su=c;
    di=d;
  }
};

int dp[1009][1009][9],n,k;
X pre[1009][1009][9],p[1009][1009][9];


int prin(int a,int c,int d){
  string ans="";
  int a1=a,d1=d,c1=c;
  while(a!=1001){
    ans+=('0'+d);
    int A=pre[a][c][d].id;

    int C=pre[a][c][d].su;
    int D=pre[a][c][d].di;
    a=A;

    c=C;
    d=D;
  }
  while(1){
    ans+=('0'+d1);
    int A=p[a1][c1][d1].id;

    int C=p[a1][c1][d1].su;
    int D=p[a1][c1][d1].di;
    a1=A;

    c1=C;
    d1=D;
    if(d1==-1)break;
  }
  reverse(ans.begin(),ans.end());
  int idx=0;
  while(ans[idx]=='0')idx++;
  for(;idx<ans.size();idx++)cout<<ans[idx];
    cout<<endl;
  exit(0);
}

int dfs(int idx,int sum=0,int dig=0){
  if(idx==1001)return sum==n;
  int &res=dp[idx][sum][dig];
  if(~res)return res;
  res=0;
  for(int i=0;i<=9;i++){
    p[idx+1][sum+i][i]=X(idx,sum,dig);
    res+=dfs(idx+1,sum+i,i);
    pre[idx][sum][dig]=X(idx+1,sum+i,i);
    if(res==k){
      prin(idx,sum,dig);
    }
  }
  return res;
}

int main(){
  memset(dp,-1,sizeof(dp));
  cin>>n>>k;
  dfs(0);
}