oj.uz

Submission #1090006

# Submission time Handle Problem Language Result Execution time Memory
1090006 2024-09-17T14:12:22 Z xnqs K-th path (IZhO11_kthpath) C++17
0 / 100
 2 ms 468 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++) {
		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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 2 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -