Submission #173737

#	Time	Username	Problem	Language	Result	Execution time	Memory
173737		juggernaut	K-th path (IZhO11_kthpath)	C++14	100 / 100	3 ms	760 KiB

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 (stderr)

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:10: 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:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&a[i]);
         ~~~~~^~~~~~~~~~~~
kthpath.cpp:24:10: 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 / 100