Submission #1084837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084837		DucNguyen2007	K-th path (IZhO11_kthpath)	C++14	0 / 100	0 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;
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++)
        {
            for(auto [x,y]:v[ch])
            {
                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;
}

Compilation message (stderr)

kthpath.cpp: In function 'int main()':
kthpath.cpp:51:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |             for(auto [x,y]:v[ch])
      |                      ^

• Subtask 1: 0 / 100