Submission #1299982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299982		Petrix	K-th path (IZhO11_kthpath)	C++20	100 / 100	1 ms	580 KiB

kthpath

#include <iostream>
#include <map>
using namespace std;
#define int long long

int dp[40][40];
string a[40];
map<pair<int,int>,int> cur,urm;
map<char,int> sum;

signed main() {
	ios_base::sync_with_stdio(false);cin.tie(NULL);
    int i,j,n,m,k  ;
	for(i=1;i<35;i++){
		for(j=1;j<35;j++){
			dp[i][j]=dp[i-1][j]+dp[i][j-1];dp[1][1]=1;
		}
	}

	cin>>n>>m;
	for(i=0;i<n;i++) cin>>a[i];
	cin>>k;string rasp(n+m-1,a[0][0]);
	cur[{0,0}]=1;
	for(i=0;i<n+m-1;i++) {
		sum.clear();
		for(auto &[poz,cnt] : cur) {
			sum[a[poz.first][poz.second]]+=dp[n-poz.first][m-poz.second]*cnt;
		}
		for(auto &[poz,cnt]:sum) {
			rasp[i]=poz;
			if(cnt<k) k-=cnt;
			else break;
		}
		for(auto &[poz,cnt]:cur) {
			if(a[poz.first][poz.second]==rasp[i]){
				if(poz.first+1!=n) urm[{poz.first+1,poz.second}]+=cnt;
				if(poz.second+1!=m) urm[{poz.first,poz.second+1}]+=cnt;
			}
		}

		cur=urm;
		urm.clear();
	}
	cout<<rasp;
	return 0;
}

• Subtask 1: 100 / 100