Submission #36297

#	Time	Username	Problem	Language	Result	Execution time	Memory
36297		Kerim	K-th path (IZhO11_kthpath)	C++14	100 / 100	29 ms	2612 KiB

kthpath

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N=33;
const ll B=1e18+5;
char arr[N][N];
ll dp[N][N][2*N],C[2*N][2*N];
int n,m,sz;
string s,t;
void normalize(ll &a,ll b){
	if(a>=B-b)
		a=B;
	else
		a+=b;	
}
ll way(int x,int y){
	return C[x+y-2][x-1];
}
ll rec(int x,int y,int pos){
	if(pos==sz-1)
		return way(n-x+1,m-y+1);
	ll &ret=dp[x][y][N];
	if(~ret)
		return ret;ret=0;
	if(x+1<=n and arr[x+1][y]==t[pos+1])
		normalize(ret,rec(x+1,y,pos+1));
	if(y+1<=m and arr[x][y+1]==t[pos+1])
		normalize(ret,rec(x,y+1,pos+1));
	return ret;
}
ll solve(string x){
	memset(dp,-1,sizeof dp);
	sz=x.size();t=x;
	return rec(1,1,0);
}
int main(){
    //~ freopen("file.in", "r", stdin);
    for(int i=0;i<N*2;i++)
		C[i][0]=1;
	for(int i=1;i<N*2;i++)
		for(int j=1;j<=i;j++){
			if(C[i-1][j]>=B-C[i-1][j-1])
				C[i][j]=B;
			else
				C[i][j]=C[i-1][j]+C[i-1][j-1];
		}
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf(" %c",&arr[i][j]);
	ll k;
	scanf("%lld",&k);		
	s+=arr[1][1];
	for(int i=0;i<n+m-2;i++)
		for(int j=0;j<26;j++){
			ll res=solve(s+char(j+97));
			if(res>=k){
				s+=char(j+97);
				break;
			}
			k-=res;
		}
	puts(s.c_str());	
	return 0;
}

Compilation message (stderr)

kthpath.cpp: In function 'int main()':
kthpath.cpp:63:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
kthpath.cpp:66:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&arr[i][j]);
                           ^
kthpath.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&k);  
                  ^

• Subtask 1: 100 / 100