Submission #89781

#	Time	Username	Problem	Language	Result	Execution time	Memory
89781		314rate	K-th path (IZhO11_kthpath)	C++14	100 / 100	4 ms	636 KiB

kthpath

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
//typedef long double ld;

const ll INF=1000000000000000000;
const ll N=30+5;

ll n,m;
ll k;
ll go[N][N];
string v[N];
ll e[N][N];

vector<pair<ll,ll>>p[2*N];

ll t[100];

ll add(ll a,ll b)
{
    a+=b;
    if(a>INF)
    {
        a=INF;
    }
    return a;
}

ll mul(ll a,ll b)
{
    if(a==0 || b==0)
    {
        return 0;
    }
    ll ans=a*b;
    if(ans%a!=0 || ans/a!=b)
    {
        return INF;
    }
    if(ans>INF)
    {
        return INF;
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(ll i=n;i>=1;i--)
    {
        for(ll j=m;j>=1;j--)
        {
            if(i==n && j==m)
            {
                go[i][j]=1;
            }
            else
            {
                go[i][j]=go[i+1][j]+go[i][j+1];
            }
        }
    }
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            ll s=i+j-1;
            p[s].push_back({i,j});
        }
    }
    for(ll i=1;i<=n;i++)
    {
        cin>>v[i];
        v[i]="."+v[i];
    }
    cin>>k;
    e[1][1]=1;
    string ans;
    ans+=v[1][1];
    for(ll di=2;di<=n+m-1;di++)
    {
        for(auto &it:p[di-1])
        {
            ll r=it.first;
            ll c=it.second;
            e[r+1][c]=add(e[r+1][c],e[r][c]);
            e[r][c+1]=add(e[r][c+1],e[r][c]);
        }
        for(ll i=0;i<26;i++)
        {
            t[i]=0;
        }
        for(auto &it:p[di])
        {
            ll r=it.first;
            ll c=it.second;
            ll f=v[r][c]-'a';
            ll a=e[r][c];
            ll b=go[r][c];
            t[f]=add(t[f],mul(a,b));
        }
        char ch;
        ll cur=0LL;
        for(ll i=0;i<26;i++)
        {
            cur+=t[i];
            if(cur<k) continue;
            cur-=t[i];
            k-=cur;
            ch=i+'a';
            break;
        }

        for(auto &it:p[di])
        {
            ll r=it.first;
            ll c=it.second;
            if(v[r][c]!=ch)
            {
                e[r][c]=0;
            }
        }
        ans+=ch;
    }
    cout<<ans<<"\n";
    return 0;
}

• Subtask 1: 100 / 100