Submission #13252

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13252	2015-02-05T16:47:57 Z	dohyun0324	K-th path (IZhO11_kthpath)	C++	100 / 100	0 ms	1588 KB

kthpath

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
char a[40][40];
int p;
int r,n,m;
long long k,cnt,d[61][31][31],ch[30],num[40][40];
char dap[61],top;
int main()
{
    int i,j;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%s",&a[i]);
        for(j=m;j>=1;j--) a[i][j]=a[i][j-1];
    }
    num[n+1][m]=1;
    for(i=n;i>=1;i--){
        for(j=m;j>=1;j--){
            num[i][j]=num[i+1][j]+num[i][j+1];
        }
    }
    scanf("%lld",&k); d[0][1][1]=1; dap[++top]=a[1][1];
    if(n==1 && m==1){printf("%c",dap[1]); return 0;}
    while(1){
        r++; memset(ch,0,sizeof ch);
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                d[r][i][j]+=d[r-1][i-1][j]+d[r-1][i][j-1];
                ch[a[i][j]-'a'+1]+=d[r][i][j]*num[i][j];
            }
        }
        for(i=1;i<=26;i++){
            if(cnt+ch[i]>k-1) break;
            cnt+=ch[i];
        }
        memset(d[r],0,sizeof d[r]); p=i;
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                if(a[i][j]-'a'+1==p) d[r][i][j]+=d[r-1][i-1][j]+d[r-1][i][j-1];
            }
        }
        dap[++top]=char(p+'a'-1);
        if(r==n+m-2) break;
    }
    for(i=1;i<=top;i++) printf("%c",dap[i]);
    return 0;
}

Compilation message

kthpath.cpp: In function 'int main()':
kthpath.cpp:15:25: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[40]' [-Wformat=]
         scanf("%s",&a[i]);
                         ^
kthpath.cpp:24:46: warning: array subscript has type 'char' [-Wchar-subscripts]
     scanf("%lld",&k); d[0][1][1]=1; dap[++top]=a[1][1];
                                              ^
kthpath.cpp:44:18: warning: array subscript has type 'char' [-Wchar-subscripts]
         dap[++top]=char(p+'a'-1);
                  ^
kthpath.cpp:13:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
                         ^
kthpath.cpp:15:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&a[i]);
                          ^
kthpath.cpp:24:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&k); d[0][1][1]=1; dap[++top]=a[1][1];
                     ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1588 KB	Output is correct
2	Correct	0 ms	1588 KB	Output is correct
3	Correct	0 ms	1588 KB	Output is correct
4	Correct	0 ms	1588 KB	Output is correct
5	Correct	0 ms	1588 KB	Output is correct
6	Correct	0 ms	1588 KB	Output is correct
7	Correct	0 ms	1588 KB	Output is correct
8	Correct	0 ms	1588 KB	Output is correct
9	Correct	0 ms	1588 KB	Output is correct
10	Correct	0 ms	1588 KB	Output is correct
11	Correct	0 ms	1588 KB	Output is correct
12	Correct	0 ms	1588 KB	Output is correct
13	Correct	0 ms	1588 KB	Output is correct
14	Correct	0 ms	1588 KB	Output is correct
15	Correct	0 ms	1588 KB	Output is correct
16	Correct	0 ms	1588 KB	Output is correct
17	Correct	0 ms	1588 KB	Output is correct
18	Correct	0 ms	1588 KB	Output is correct
19	Correct	0 ms	1588 KB	Output is correct
20	Correct	0 ms	1588 KB	Output is correct