oj.uz

답안 #1090010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1090010 2024-09-17T14:16:43 Z xnqs K번째 경로 (IZhO11_kthpath) C++17
100 / 100
 54 ms 600 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>

int x, y;
int64_t k;
char arr[30][31];

int64_t count_solutions(const std::string& tgt) {
	std::vector<std::vector<std::vector<int64_t>>> dp(x,std::vector<std::vector<int64_t>>(y,std::vector<int64_t>(2,-1)));

	const std::function<int64_t(int,int,int)> sol = [&](int i, int j, int tight) {
		if (i==x-1&&j==y-1) {
			return static_cast<int64_t>(1);
		}
		if (dp[i][j][tight]!=-1) {
			return dp[i][j][tight];
		}

		int64_t ret = 0;
		if (i+1<x &&
		    ((tight) ? arr[i+1][j]<=tgt[i+1+j] : 1)) {
			ret += sol(i+1,j,tight&(arr[i+1][j]==tgt[i+1+j]));
		}
		if (j+1<y &&
		    ((tight) ? arr[i][j+1]<=tgt[i+j+1] : 1)) {
			ret += sol(i,j+1,tight&(arr[i][j+1]==tgt[i+j+1]));
		}

		return dp[i][j][tight] = ret;
	};

	return sol(0,0,1);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> y;
	for (int i = 0; i < x; i++) {
		std::cin >> arr[i];
	}
	std::cin >> k;

	std::string tgt(x+y-1,'z');
	tgt[0] = arr[0][0];
	tgt[x+y-2] = arr[x-1][y-1];

	for (int i = 1; i < x+y-2; i++) {
		char best = 'z';
		for (int j = 'z'; j >= 'a'; j--) {
			tgt[i] = j;
			if (count_solutions(tgt)>=k) {
				best = j;
			}
		}

		tgt[i] = best;
	}

	std::cout << tgt << "\n";
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 6 ms 456 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 17 ms 484 KB Output is correct
11 Correct 5 ms 464 KB Output is correct
12 Correct 19 ms 600 KB Output is correct
13 Correct 28 ms 348 KB Output is correct
14 Correct 27 ms 496 KB Output is correct
15 Correct 46 ms 348 KB Output is correct
16 Correct 54 ms 348 KB Output is correct
17 Correct 49 ms 344 KB Output is correct
18 Correct 49 ms 348 KB Output is correct
19 Correct 52 ms 344 KB Output is correct
20 Correct 51 ms 352 KB Output is correct