Submission #338179

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

kthpath

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

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 / 100