oj.uz

Submission #338179

# Submission time Handle Problem Language Result Execution time Memory
338179 2020-12-22T15:51:24 Z juggernaut K-th path (IZhO11_kthpath) C++14
100 / 100
 3 ms 364 KB 
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=33;
char arr[N][N],ans[N+N];
ll dp[N][N];
int n,m,len;
ll rec(int x,int y){
	int pos=x+y;
	if(ans[pos]!='*' and ans[pos]!=arr[x][y])
		return 0;
	if(x==n-1 and y==m-1)
		return 1;
	ll &ret=dp[x][y];
	if(~ret)
		return ret;
	ret=0;
	if(x+1<n)
		ret+=rec(x+1,y);
	if(y+1<m)
		ret+=rec(x,y+1);
	return ret;	
}
int main(){
	scanf("%d%d",&n,&m); len=n+m-1;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf(" %c",&arr[i][j]);
	ll k;
	scanf("%lld",&k);
	for(int i=0;i<len;i++)
		ans[i]='*';
	ans[0]=arr[0][0];
	for(int i=1;i<len;i++)
		for(int j=0;j<26;j++){
			ans[i]=j+'a';
			memset(dp,-1,sizeof dp);
			if(rec(0,0)>=k)
				break;
			k-=rec(0,0);	
		}
	printf("%s\n",ans);
	return 0;
}

Compilation message

kthpath.cpp: In function 'int main()':
kthpath.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  scanf("%d%d",&n,&m); len=n+m-1;
      |  ~~~~~^~~~~~~~~~~~~~
kthpath.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |    scanf(" %c",&arr[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~
kthpath.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  scanf("%lld",&k);
      |  ~~~~~^~~~~~~~~~~

Subtask #1
100.0 / 100.0

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