Submission #1084940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084940		DucNguyen2007	K-th path (IZhO11_kthpath)	C++14	0 / 100	1 ms	344 KiB

kthpath

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=101;
const ll inf=2e18;
int n,m;
ll dp[maxN+1][maxN+1][maxN+1],k;
char c[maxN+1][maxN+1];
vector<pii> v[26];
string s;
bool check(int i,int j,int x,int y)
{
    if(i+1==x&&j==y)
    {
        return true;
    }
    if(i==x&&j+1==y)
    {
        return true;
    }
    return false;
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            cin>>c[i][j];
            v[c[i][j]-'a'].push_back({i,j});
        }
    }
    cin>>k;
    dp[0][1][1]=1;
    for(int st=1;st<=n+m-2;st++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                dp[st][i][j]+=(dp[st-1][i-1][j]+dp[st-1][i][j-1]);
            }
        }
    }
    s="";
    s+=c[n][m];
    for(int st=n+m-3;st>=1;st--)
    {
        ll res=0,cur=0;
        for(int ch=0;ch<26;ch++)
        {
            bool ok=false;
            if(st==n+m-3)
            {
                for(auto [x,y]:v[ch])
                {
                    if(check(x,y,n,m))
                    {
                        ok=true;
                        break;
                    }
                }
            }
            else
            {
                for(auto [x,y]:v[ch])
                {
                    for(auto [i,j]:v[s[s.size()-1]-'a'])
                    {
                        if(check(x,y,i,j))
                        {
                            ok=true;
                            break;
                        }
                    }
                    if(ok)
                    {
                        break;
                    }
                }
            }
            if(!ok)
            {
                continue;
            }
            for(auto [x,y]:v[ch])
            {
                for(auto [i,j]:v[s[s.size()-1]-'a'])
                {
                    if(check(x,y,i,j))
                    {
                        res+=dp[st][x][y];
                    }
                }
            }
            if(res>=k)
            {
                s+=(char)(ch+'a');
                k-=cur;
                //cout<<st<<" "<<ch<<'\n';
                break;
            }
            cur=res;
        }
    }
    s+=c[1][1];
    //reverse(s.begin(),s.end());
    cout<<s;
}
/*2 3
abc
def
3*/

Compilation message (stderr)

kthpath.cpp: In function 'int main()':
kthpath.cpp:66:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |                 for(auto [x,y]:v[ch])
      |                          ^
kthpath.cpp:77:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |                 for(auto [x,y]:v[ch])
      |                          ^
kthpath.cpp:79:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |                     for(auto [i,j]:v[s[s.size()-1]-'a'])
      |                              ^
kthpath.cpp:97:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |             for(auto [x,y]:v[ch])
      |                      ^
kthpath.cpp:99:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |                 for(auto [i,j]:v[s[s.size()-1]-'a'])
      |                          ^

• Subtask 1: 0 / 100