oj.uz

Submission #1110439

# Submission time Handle Problem Language Result Execution time Memory
1110439 2024-11-09T12:50:30 Z Tsagana K-th path (IZhO11_kthpath) C++14
0 / 100
 1124 ms 262144 KB 
#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 {
	multiset<pair<int, int>> s[30];
};

pos s[70];
lnl dis[35][35];
char c[35][35];
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 = 1; i <= n; i++)
	for (int j = 1; j <= m; j++)
		cin >> c[i][j];
}
lnl calc(int i, int j) {
	lnl 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[1].s[c[1][1]-'a'].insert({1, 1});
	for (int i = 1; i <= n+m; i++) {
		for (int j = 0; j < 26; j++) {
			lnl x = calc(i, j);
			if (x >= k) {
				ans += (j+'a');
				put(i, j);
				break ;
			}
			k -= x;
			if (k < 0) exit(0);
		}
	}
	cout << ans;
}
int main() {IOS solve(); return 0;}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 576 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Runtime error 1124 ms 262144 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -