Submission #1090006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090006		xnqs	K-th path (IZhO11_kthpath)	C++17	0 / 100	2 ms	468 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++) {
		while (1) {
			std::string tmp = tgt;
			tmp[i] -= 1;
			//std::cout << tmp << " " << count_solutions(tmp) << "\n";
			if (tmp[i]=='a'||count_solutions(tmp)<k) {
				break;
			}

			tgt[i] -= 1;
		}
	}

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

• Subtask 1: 0 / 100