제출 #1090010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1090010		xnqs	K-th path (IZhO11_kthpath)	C++17	100 / 100	54 ms	600 KiB

kthpath

#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 / 100