oj.uz

답안 #1109716

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109716 2024-11-07T11:07:21 Z Tsagana K번째 경로 (IZhO11_kthpath) C++14
0 / 100
 1 ms 548 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[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) {
	lnl ans = 0;
	if (!s[i].s[j].empty()) 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;
	if (k > dis[n][m]) exit(1);
	string ans = "";
	
	s[0].s[c[0][0]-'a'].insert({0, 0});
	for (int i = 0; i <= n+m; i++) {
		for (int j = 0; j < 26; j++) {
			lnl x = calc(i, j);
			// if (!s[i].s[j].empty())
			// 	cout << i << ' ' << char(j+'a') << ' ' << x << ' ' << k << '\n';
			if (x >= k) {
				ans += j + 'a';
				put(i, j);
				break ;
			}
			k -= x;
		}
	}
	cout << ans;
}
int main() {IOS solve(); return 0;}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 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 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 548 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Incorrect 1 ms 336 KB Output isn't correct
11 Halted 0 ms 0 KB -