# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
895369 | presko | K-th path (IZhO11_kthpath) | C++14 | 1 ms | 604 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |