Submission #1325848

#TimeUsernameProblemLanguageResultExecution timeMemory
1325848vtnooK-th path (IZhO11_kthpath)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()
#define sz(a) ((int) a.size())
#define pb push_back
#define fst first
#define snd second
using namespace std;
typedef unsigned long long ll;
ll dp[30][30];
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(nullptr);
	int n,m;cin>>n>>m;
	vector<string>g(n);
	L(i,0,n-1)cin>>g[i];
	ll k;cin>>k;
	dp[n-1][m-1]=1;
	R(i,n-1,0){
		R(j,m-1,0){
			int ni=i-1,nj=j-1;
			if(ni>=0)dp[ni][j]+=dp[i][j];
			if(nj>=0)dp[i][nj]+=dp[i][j];
		}
	}
	string ans(1,g[0][0]);
	vector<pair<int,int>>path;
	path.pb({0,0});
	L(i,0,n+m-1){
		bool vis[30][30];
		memset(vis,0,sizeof(vis));
		vector<pair<int,int>>nxtPath;
		for(auto [x,y]:path){
			if(x+1<n&&!vis[x+1][y]){
				nxtPath.pb({x+1,y});
				vis[x+1][y]=true;
			}
			if(y+1<m&&!vis[x][y+1]){
				nxtPath.pb({x,y+1});
				vis[x][y+1]=true;
			}
		}
		for(char c='a';c<='z';c++){
			ll ways=0;
			for(auto [x,y]:nxtPath)if(g[x][y]==c){
				ways+=dp[x][y];
			}
			if(ways>=k){
				ans+=c;
				path.clear();
				for(auto [x,y]:nxtPath)if(g[x][y]==c){
					path.pb({x,y});
				}
				break;
			}else{
				k-=ways;
			}
		}
	}
	cout<<ans<<endl;
}

#Verdict Execution timeMemoryGrader output
Fetching results...