# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
881098 | alexdd | K-th path (IZhO11_kthpath) | C++17 | 2 ms | 452 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<iostream>
using namespace std;
#define int long long
const int INF = 1e18;
int n,m,k;
string s;
char mat[35][35];
int dp[35][35][2];
int calc()
{
dp[1][1][1] = 1;
dp[1][1][0] = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i==1 && j==1)
continue;
if(mat[i][j]==s[i+j-1])
{
dp[i][j][1] = min(INF+5, dp[i-1][j][1] + dp[i][j-1][1]);
dp[i][j][0] = min(INF+5, dp[i-1][j][0] + dp[i][j-1][0]);
}
else if(mat[i][j] < s[i+j-1])
{
dp[i][j][1] = 0;
dp[i][j][0] = min(INF+5, dp[i-1][j][0] + dp[i-1][j][1] + dp[i][j-1][0] + dp[i][j-1][1]);
}
else
{
dp[i][j][1] = 0;
dp[i][j][0] = min(INF+5, dp[i-1][j][0] + dp[i][j-1][0]);
}
}
}
return min(INF+5, dp[n][m][0]);
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>mat[i][j];
}
}
cin>>k;
s = "#";
s.push_back(mat[1][1]);
for(int i=2;i<=n+m-1;i++)
{
s.push_back('a'-1);
}
for(int i=2;i<=n+m-1;i++)
{
for(int j=26-1;j>=0;j--)
{
s[i] = j + 'a';
if(calc() <= k-1)
{
break;
}
}
}
for(int i=1;i<=n+m-1;i++)
cout<<s[i];
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |