Submission #1109229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109229		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;

lnl dis[31][31];
char c[31][31];

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 solve () {
	build();
	int x, y; cin >> x >> y; x--; y--;
	for (int i = x; i >= 0; i--) {
		for (int j = y; j >= 0; j--) {
			cin >> c[i][j];
		}
	}

	int k; cin >> k;
	string ans = "";

	while (x || y) {
		if (!x) {ans += c[x][y]; y--; continue ;}
		if (!y) {ans += c[x][y]; x--; continue ;}

		ans += c[x][y];

		if (c[x][y-1] <= c[x-1][y]) {
			if (dis[x][y-1] >= k) {y--;}
			else {x--; k -= dis[x][y];}
		}
		else {
			if (dis[x-1][y] >= k) {x--;}
			else {y--; k -= dis[x][y];}
		}
	}
	ans += c[0][0];
	cout << ans;
}
int main() {IOS solve(); return 0;}

• Subtask 1: 0 / 100