結果

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

テストケース

テストケース	結果	得点	実行時間	メモリ使用量
1	WA	0%	121ms	115728KB
2	WA	0%	104ms	115744KB
3	WA	0%	122ms	115744KB
4	WA	0%	117ms	115728KB
5	WA	0%	108ms	115744KB
6	WA	0%	110ms	115728KB
7	WA	0%	126ms	115728KB
8	WA	0%	117ms	115744KB
9	WA	0%	113ms	115728KB
10	WA	0%	100ms	115744KB
11	WA	0%	113ms	115728KB
12	WA	0%	130ms	115728KB
13	WA	0%	140ms	115744KB
14	WA	0%	117ms	115744KB
15	WA	0%	145ms	115744KB
16	WA	0%	102ms	115744KB
17	WA	0%	119ms	115728KB
18	WA	0%	108ms	115744KB
19	WA	0%	96ms	115728KB
20	WA	0%	115ms	115728KB
21	WA	0%	124ms	115728KB
22	WA	0%	119ms	115744KB
23	WA	0%	113ms	115728KB
24	WA	0%	136ms	115744KB
25	WA	0%	112ms	115744KB
26	WA	0%	110ms	115728KB
27	WA	0%	142ms	115728KB
28	WA	0%	110ms	115728KB
29	WA	0%	115ms	115728KB
30	WA	0%	121ms	115744KB
31	WA	0%	134ms	115744KB
32	WA	0%	118ms	115728KB
33	WA	0%	97ms	115728KB
34	WA	0%	122ms	115728KB
35	WA	0%	114ms	115744KB
36	WA	0%	110ms	115728KB
37	WA	0%	117ms	115728KB
38	WA	0%	118ms	115728KB
39	WA	0%	110ms	115744KB
40	WA	0%	112ms	115728KB
41	WA	0%	111ms	115728KB
42	WA	0%	120ms	115744KB
43	WA	0%	125ms	115744KB
44	WA	0%	100ms	115744KB
45	WA	0%	100ms	115728KB
46	WA	0%	114ms	115744KB
47	WA	0%	106ms	115744KB
48	WA	0%	108ms	115744KB
49	WA	0%	103ms	115728KB
50	WA	0%	114ms	115728KB
51	WA	0%	16ms	115744KB

ソースコード

#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){
    id=a;

    su=c;
    
  }
};


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


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

    int C=pre[a][c].su;
    int D=abs(c-C);
    a=A;

    c=C;
    d=D;
    ans+=('0'+d);
  }
  reverse(ans.begin(),ans.end());
  if(!(c1==0&&p[a1][c1].su==0))
  while(1){
    int A=p[a1][c1].id;

    int C=p[a1][c1].su;
    int D=abs(c1-C);
    a1=A;

    c1=C;
    d1=D;
    ans+=('0'+d1);
    if(c1==0)break;
  }
  reverse(ans.begin(),ans.end());
  int idx=0;
  cout<<ans<<endl;
  exit(0);
}

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

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

結果

テストケース

ALL0%/100%

ソースコード