Submission #1109092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109092		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 n, m; cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> c[i][j];
		}
	}
	int k; cin >> k;
	n--; m--;
	int x = 0, y = 0;
	string ans;
	while (x != n || y != m) {
		//cout << x << ' ' << y << ' ' << n << ' ' << m << ' ' << k << '\n';
		ans += c[x][y];
		if (x == n) {
			while (y != m) {
				y++;
				ans += c[x][y];
			}
			break ;
		}
		if (y == m) {
			while (x != n) {
				x++;
				ans += c[x][y];
			}
			break ;
		}
		if (c[x+1][y] > c[x][y+1]) {
			if (dis[n-x][m-y-1] < k) {k -= dis[n-x][m-y-1]; x++;}
			else y++;
		}
		else {
			if (dis[n-x-1][m-y] < k) {k -= dis[n-x-1][m-y]; y++;}
			else x++;
		}
	}
	cout << ans;
}
int main() {IOS solve(); return 0;}

• Subtask 1: 0 / 100