Submission #730174

#TimeUsernameProblemLanguageResultExecution timeMemory
730174fdnfksdK-th path (IZhO11_kthpath)C++14
100 / 100
2 ms724 KiB
#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 (stderr)

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;
      |                      ^~
#Verdict Execution timeMemoryGrader output
Fetching results...