oj.uz

답안 #41184

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
41184 2018-02-13T16:44:56 Z alenam0161 K번째 경로 (IZhO11_kthpath) C++14
0 / 100
 762 ms 262144 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
const int N = 3e1 + 7;
long long dp[N][N];
string a[N];
long long C[N];
int main() {
	//freopen("input.txt", "r", stdin);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; ++i)cin >> a[i];
	for(int i=n-1;i>=0;i--)
		for (int j = m - 1; j >= 0; j--) {
			if (i == n - 1 && j == m - 1)dp[i][j] = 1;
			else dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
		}
	long long k;
	cin >> k;
	string ans = "";
	vector<pair<int, int>> v,cur;
	v.push_back({ 0,0 });
	for (int i = 0; i < (n + m)-1; ++i) {
		for (int j = 0; j < 26; ++j)C[j] = 0;
		if (i == 0) {
			ans += a[v[0].first][v[0].second];
		}
		for (int j = 0; j < v.size(); ++j) {
			if (v[j].first + 1 < n) {
				C[a[v[j].first + 1][v[j].second]-'a'] += dp[v[j].first + 1][v[j].second];
			}
			if (v[j].second + 1 < m) {
				C[a[v[j].first][v[j].second + 1]-'a'] += dp[v[j].first][v[j].second + 1];
			}
		}
		for (int j = 0; j < 26; ++j) {
			if (C[j] < k) {
				k -= C[j];
			}
			else {
				ans += char(j + 'a');
				cur.clear();
				for (int c = 0; c < v.size(); ++c) {
					if (v[c].first + 1 < n&&a[v[c].first + 1][v[c].second] - 'a' == j) {
						cur.push_back({ v[c].first + 1,v[c].second });
					}
					if (v[c].second + 1 < m&&a[v[c].first][v[c].second + 1] - 'a' == j) {
						cur.push_back({ v[c].first,v[c].second + 1 });
					}
				}
				v = cur;
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Compilation message

kthpath.cpp: In function 'int main()':
kthpath.cpp:31:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size(); ++j) {
                     ^
kthpath.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int c = 0; c < v.size(); ++c) {
                       ^

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 572 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Correct 2 ms 616 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 624 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Runtime error 762 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -