#include<iostream>
#include<bits/stdc++.h>
#define MAXN 110
using namespace std;
char tab[MAXN][MAXN];
string ways[MAXN][MAXN];
string add(string res, string curr)
{
if(res=="")return curr;
if(curr=="")return res;
string ret="";
int lastres=res.size()-1,lastcurr=curr.size()-1,carry=0;
while(lastres>-1 && lastcurr>-1)
{
int digres = res[lastres]-'0';
int digcurr = curr[lastcurr]-'0';
ret+=(digres+digcurr+carry)%10+'0';
carry=(digres+digcurr+carry)/10;
lastres--;
lastcurr--;
}
if(lastres>-1)
{
while(lastres>-1)
{
int digres = res[lastres]-'0';
ret+=(digres+carry)%10+'0';
carry=(digres+carry)/10;
lastres--;
}
}
else if(lastcurr>-1)
{
while(lastcurr>-1)
{
int digcurr = curr[lastcurr]-'0';
ret+=(digcurr+carry)%10+'0';
carry=(digcurr+carry)/10;
lastcurr--;
}
}
if(carry>0)ret+=(carry+'0');
reverse(ret.begin(),ret.end());
return ret;
}
int cmp(string x, string y)
{
if(x.size()<y.size())return -1;
else if(x.size()>y.size())return 1;
for(int i=0;i<x.size();i++)
{
if(x[i]!=y[i])
{
if(x[i]>y[i])return 1;
else return -1;
}
}
return 0;
}
int main()
{
int n,m;
string k;
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char c;
cin>>c;
if(i==1 && j==1)ways[i][j]="1";
else ways[i][j]=add(ways[i-1][j],ways[i][j-1]);
tab[i][j]=c;
}
}
cin>>k;
cout<<tab[1][1];
int x=1,y=1;
string l="1";
while(x<n || y<m)
{
bool fl1=0,fl2=0;
string down="",right="";
if(y<m)right=ways[n-x+1][m-y];//check right
else fl1=1;
if(x<n)down=ways[n-x][m-y+1];//check down
else fl2=1;
if(fl1)
{
x++;
cout<<tab[x][y];
}
else if(fl2)
{
y++;
cout<<tab[x][y];
}
else
{
if(tab[x][y+1]<=tab[x+1][y])
{
string lim=add(l,right);
if(cmp(k,lim)==-1){y++;cout<<tab[x][y];}
else {x++;l=lim;cout<<tab[x][y];}
}
else
{
string lim=add(l,down);
if(cmp(k,lim)==-1){x++;cout<<tab[x][y];}
else {y++;l=lim;cout<<tab[x][y];}
}
}
}
cout<<"\n";
}
Compilation message
kthpath.cpp: In function 'int cmp(std::string, std::string)':
kthpath.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i=0;i<x.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
