Submission #883697

#	Time	Username	Problem	Language	Result	Execution time	Memory
883697		heeheeheehaaw	K-th path (IZhO11_kthpath)	C++17	0 / 100	1 ms	604 KiB

kthpath

#include <bits/stdc++.h>
#define int long long

using namespace std;

int comb[100][100];
int a[100][100];
bool visited[100][100];
string from[100][100];
int dx[] = {0, 1};
int dy[] = {1, 0};
int apare[100];
int cnt[100][100];
const int llm = 1e18;

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;
    if(n > 15)
        while(1);
    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((int)comb[i - 1][j] + comb[i - 1][j - 1] >= llm || comb[i - 1][j] == llm || 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";
    cnt[1][1] = 1;
    while(!v.empty())
    {
        if(v[0].first == n && v[0].second == m)
            break;

        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)
                    continue;
                int cv = calc(nx, ny, n, m);
                if(cv <= llm / cnt[x][y])
                    cv *= cnt[x][y];
                else
                    cv = llm;
                cv = min(cv, llm);
                apare[a[nx][ny]] += cv;
                cnt[nx][ny] += cnt[x][y];
                cnt[nx][ny] = min(cnt[nx][ny], llm);
                apare[a[nx][ny]] = min(apare[a[nx][ny]], llm);
                aux.push_back({nx, ny});
            }
        }

        aux.clear();
        int ch;
        for(int i = 1; i <= 26; i++)
        {
            if(apare[i] != 0)
            {
                int newc = (int)curr + apare[i];
                newc = min(newc, llm);
                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)

kthpath.cpp: In function 'int main()':
kthpath.cpp:113:55: warning: 'ch' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |                 from[nx][ny].push_back((char)ch + 'a' - 1);
      |                                        ~~~~~~~~~~~~~~~^~~

• Subtask 1: 0 / 100