oj.uz

Submission #173737

# Submission time Handle Problem Language Result Execution time Memory
173737 2020-01-05T09:21:17 Z juggernaut K-th path (IZhO11_kthpath) C++14
100 / 100
 3 ms 760 KB 
#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: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.0 / 100.0

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