Submission #1326220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326220		vtnoo	K-th path (IZhO11_kthpath)	C++20	100 / 100	4 ms	332 KiB

kthpath

#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()
#define sz(a) ((int) a.size())
#define pb push_back
#define fst first
#define snd second
using namespace std;
typedef long long ll;
const int N=30;
ll dp[N][N][2];
string g[N];
ll ways(int n,int m,string s){
	L(i,0,N-1)L(j,0,N-1)L(k,0,2)dp[i][j][k]=0;
	dp[0][0][0]=1;
	L(i,0,n-1){
		L(j,0,m-1){
			if(i>0){
				dp[i][j][1]+=dp[i-1][j][1];
				if(g[i][j]<=s[i+j])dp[i][j][g[i][j]!=s[i+j]]+=dp[i-1][j][0];
			}
			if(j>0){
				dp[i][j][1]+=dp[i][j-1][1];
				if(g[i][j]<=s[i+j])dp[i][j][g[i][j]!=s[i+j]]+=dp[i][j-1][0];
			}
		}
	}
	return dp[n-1][m-1][0]+dp[n-1][m-1][1];
}
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(nullptr);
	int n,m;cin>>n>>m; 
	L(i,0,n-1)cin>>g[i];
	ll k;cin>>k;
	string ans(1,g[0][0]);
	L(i,1,n+m-2){
		for(char c='a';c<='z';c++){
			string s=ans+c;
			s.resize(n+m-1,'z');
			if(ways(n,m,s)>=k){
				ans+=c;
				break;
			}
		}
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

kthpath.cpp: In function 'll ways(int, int, std::string)':
kthpath.cpp:15:48: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   15 |         L(i,0,N-1)L(j,0,N-1)L(k,0,2)dp[i][j][k]=0;
      |                                     ~~~~~~~~~~~^~
kthpath.cpp:2:39: note: within this loop
    2 | #define L(i, j, k) for(int i = (j); i <= (k); i++)
      |                                       ^
kthpath.cpp:15:29: note: in expansion of macro 'L'
   15 |         L(i,0,N-1)L(j,0,N-1)L(k,0,2)dp[i][j][k]=0;
      |                             ^

• Subtask 1: 100 / 100