Submission #1109678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109678		Tsagana	K-th path (IZhO11_kthpath)	C++14	0 / 100	1 ms	336 KiB

kthpath

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

struct pos {
	set<pair<int, int>> s[30];
};

pos s[61];
lnl dis[31][31];
char c[31][31];
int n, m;

void build() {
	dis[0][0] = 1;
	for (int i = 0; i <= 30; i++) {
		for (int j = 0; j <= 30; j++) {
			if (i) dis[i][j] += dis[i-1][j];
			if (j) dis[i][j] += dis[i][j-1];
		}
	}
}
void init() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++)
			cin >> c[i][j];
	n--; m--;
}
int calc(int i, int j) {
	int ans = 0;
	for (auto p: s[i].s[j]) {
		ans += dis[n-p.F][m-p.S];
	}
	return ans;
}
void put(int i, int j) {
	for (auto p: s[i].s[j]) {
		if (p.F < n) s[i+1].s[c[p.F+1][p.S]-'a'].insert({p.F+1, p.S});
		if (p.S < m) s[i+1].s[c[p.F][p.S+1]-'a'].insert({p.F, p.S+1});
	}
}
void solve () {
	build();
	init();

	lnl k; cin >> k;
	string ans = "";
	
	s[0].s[c[0][0]-'a'].insert({0, 0});
	for (int i = 0; i <= n+m-1; i++) {
		for (int j = 0; j < 26; j++) {
			int x = calc(i, j);
			if (x >= k) {
				ans += j + 'a';
				put(i, j);
				break ;
			}
			k -= x;
		}
	}
	ans += c[n][m];
	cout << ans;
}
int main() {IOS solve(); return 0;}

• Subtask 1: 0 / 100