oj.uz

Submission #41192

# Submission time Handle Problem Language Result Execution time Memory
41192 2018-02-13T17:05:14 Z alenam0161 K-th path (IZhO11_kthpath) C++14
100 / 100
 5 ms 920 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
const int N = 3e3 + 7;
long long dp[N][N];
string a[N];
long long C[N];
int main() {
	//freopen("input.txt", "r", stdin);
	int n, m;
	cin >> n >> m;
	for (int i = n - 1; i >= 0; i--)
		for (int j = m - 1; j >= 0; j--) {
			if (i == n - 1 && j == m - 1)dp[i][j] = 1;
			else dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
		}
	for (int i = 0; i < n; ++i)cin >> a[i];

	
	long long k;
	cin >> k;
	string ans = "";
	map<pair<int, int>,long long> v,cur;
	v[{0, 0}] = 1;
	for (int i = 0; i < (n + m)-1; ++i) {
		for (int j = 0; j < 26; ++j)C[j] = 0;
		if (i == 0) {
			ans += a[v.begin()->first.first][v.begin()->first.second];
		}
		for (auto to:v) {
			if (to.first.first + 1 < n) {
				C[a[to.first.first + 1][to.first.second]-'a'] += to.second*dp[to.first.first+ 1][to.first.second];
			}
			if (to.first.second + 1 < m) {
				C[a[to.first.first][to.first.second + 1]-'a'] += to.second*dp[to.first.first][to.first.second + 1];
			}
		}
		for (int j = 0; j < 26; ++j) {
			if (C[j] < k) {
				k -= C[j];
			}
			else {
				ans += char(j + 'a');
				cur.clear();
				for (auto to:v) {
					if (to.first.first + 1 < n&&a[to.first.first + 1][to.first.second] - 'a' == j) {
						cur[{ to.first.first + 1,to.first.second }]+=to.second;
					}
					if (to.first.second + 1 < m&&a[to.first.first][to.first.second + 1] - 'a' == j) {
						cur[{ to.first.first,to.first.second + 1 }]+=to.second;
					}
				}
				v = cur;
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 2 ms 712 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 2 ms 756 KB Output is correct
10 Correct 2 ms 916 KB Output is correct
11 Correct 2 ms 916 KB Output is correct
12 Correct 2 ms 916 KB Output is correct
13 Correct 2 ms 916 KB Output is correct
14 Correct 2 ms 916 KB Output is correct
15 Correct 2 ms 916 KB Output is correct
16 Correct 2 ms 916 KB Output is correct
17 Correct 2 ms 916 KB Output is correct
18 Correct 2 ms 920 KB Output is correct
19 Correct 2 ms 920 KB Output is correct
20 Correct 2 ms 920 KB Output is correct