# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
883679 | heeheeheehaaw | K-th path (IZhO11_kthpath) | C++17 | 0 ms | 348 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int comb[62][62];
int a[32][32];
bool visited[32][32];
string from[32][32];
int dx[] = {0, 1};
int dy[] = {1, 0};
int apare[32];
const int llm = 1000000000000000001;
int calc(int x, int y, int n, int m)
{
return comb[n - x + m - y][m - y];
}
signed main()
{
int n, m, k;
cin>>n>>m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
char c;
cin>>c;
a[i][j] = (int)c - 'a' + 1;
}
cin>>k;
for(int i = 0; i <= 60; i++)
comb[i][0] = 1, comb[i][i] = 1;
for(int i = 1; i <= 60; i++)
for(int j = 1; j < i; j++)
{
if(comb[i - 1][j] + comb[i - 1][j - 1] >= llm)
comb[i][j] == llm;
else
comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
}
vector<pair<int, int>> v;
int curr = 0;
v.push_back({1, 1});
from[1][1] = "a";
while(!v.empty())
{
vector<pair<int, int>> aux;
for(int i = 1; i <= 26; i++)
apare[i] = 0;
for(auto it : v)
{
int x = it.first, y = it.second;
for(int dir = 0; dir < 2; dir++)
{
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx < 1 || nx > n || ny < 1 || ny > m || visited[nx][ny])
continue;
visited[nx][ny] = true;
apare[a[nx][ny]] += calc(nx, ny, n, m);
if(apare[a[nx][ny]] >= llm)
apare[a[nx][ny]] = llm;
aux.push_back({nx, ny});
}
}
for(auto it : aux)
visited[it.first][it.second] = false;
aux.clear();
int ch;
for(int i = 1; i <= 26; i++)
{
if(apare[i] != 0)
{
int newc = curr + apare[i];
if(k > curr && k <= newc)
{
ch = i;
break;
}
else
{
curr = newc;
}
}
}
for(auto it : v)
{
int x = it.first, y = it.second;
for(int dir = 0; dir < 2; dir++)
{
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx < 1 || nx > n || ny < 1 || ny > m || visited[nx][ny] || a[nx][ny] != ch)
continue;
visited[nx][ny] = true;
aux.push_back({nx, ny});
from[nx][ny] = from[x][y];
from[nx][ny].push_back((char)ch + 'a' - 1);
}
}
v = aux;
}
cout<<from[n][m];
return 0;
}
/**
3 4
abcd
efdg
hijk
4
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |