oj.uz

Submission #730174

# Submission time Handle Problem Language Result Execution time Memory
730174 2023-04-25T11:32:45 Z fdnfksd K-th path (IZhO11_kthpath) C++14
100 / 100
 2 ms 724 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,q;
char a[1005][1005];
vector<pli>vec[3000];
bool cmp(pli x,pli y)
{
    return a[x.fi][x.se]<a[y.fi][y.se];
}
ll dp[2002][2002],c[2002][2002];
const ll maxk=1e18+10;
void solve()
{
    ll o;
    //cin >> o;
    cin >> n >> m ;
    q=1;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin >> s;
        for(int j=1;j<=m;j++)
        {
            a[i][j]=s[j-1];
            vec[i+j].pb({i,j});
        }
    }
    c[n][m]=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            c[i][j]+=c[i+1][j]+c[i][j+1];
            c[i][j]=min(c[i][j],maxk);
        }
    }
    for(int i=1;i<=m+n;i++) sort(vec[i].begin(),vec[i].end(),cmp);
    while(q--)
    {
        ll k;
        cin >> k;
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dp[i][j]=0;
        dp[1][1]=1;
        cout << a[1][1];
        for(int i=3;i<=m+n;i++)
        {
            ll sum=0;
            for(auto cc:vec[i])
            {
                dp[cc.fi][cc.se]+=dp[cc.fi-1][cc.se]+dp[cc.fi][cc.se-1];
                dp[cc.fi][cc.se]=min(dp[cc.fi][cc.se],k);
            }
            char vc;
            for(auto cc:vec[i])
            {
                ll e;
                if(k/c[cc.fi][cc.se]<dp[cc.fi][cc.se]) e=k;
                else e=dp[cc.fi][cc.se]*c[cc.fi][cc.se];
                sum+=e;
                if(sum>=k)
                {
                    vc=a[cc.fi][cc.se];
                    break;
                }
            }
            cout << vc;
            for(auto cc:vec[i])
            {
                if(a[cc.fi][cc.se]<vc) k-=dp[cc.fi][cc.se]*c[cc.fi][cc.se],dp[cc.fi][cc.se]=0;
                else if(a[cc.fi][cc.se]>vc) dp[cc.fi][cc.se]=0;
            }

        }cout << '\n';
    }
    //cout << dp[1][2]<<' '<<a[1][2];
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

kthpath.cpp: In function 'void solve()':
kthpath.cpp:24:8: warning: unused variable 'o' [-Wunused-variable]
   24 |     ll o;
      |        ^
kthpath.cpp:80:22: warning: 'vc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |                 else if(a[cc.fi][cc.se]>vc) dp[cc.fi][cc.se]=0;
      |                      ^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 536 KB Output is correct
7 Correct 1 ms 536 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 408 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 664 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 672 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 1 ms 664 KB Output is correct
19 Correct 1 ms 668 KB Output is correct
20 Correct 1 ms 668 KB Output is correct