# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
156233 | mdn2002 | Jetpack (COCI16_jetpack) | C++14 | 169 ms | 15992 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<bits/stdc++.h>
using namespace std;
long long mod=1e9+7;
int n,dp[14][100005];
char gr[14][100005];
int f(int x,int y,int up)
{
if(y==n)return true;
if(gr[x][y]=='X')return false;
if(dp[x][y]!=-1)return dp[x][y];
int pos=false;
pos=max(pos,f(max(0,x-1),y+1,1));
pos=max(pos,f(min(9,x+1),y+1,0));
return dp[x][y]=pos;
}
vector<int>a,b;
void dfs(int x,int y,int up,int time)
{
if(y==n-1)
{
cout<<a.size()<<endl;
if(time!=0)b.push_back(time);
for(int i=0;i<a.size();i++)cout<<a[i]<<' '<<b[i]<<endl;
exit(0);
}
int nx=max(0,x-1),ny=y+1;
if(dp[nx][ny]==1)
{
if(up==1)dfs(nx,ny,1,time+1);
else
{
a.push_back(y+1);
dfs(nx,ny,1,time+1);
}
}
nx=min(9,x+1),ny=y+1;
if(dp[nx][ny]==1)
{
if(up==1)
{
b.push_back(time);
dfs(nx,ny,0,0);
}
else dfs(nx,ny,0,0);
}
}
int main()
{
memset(dp,-1,sizeof dp);
cin>>n;
for(int i=0;i<10;i++)
{
for(int j=0;j<n;j++)cin>>gr[i][j];
}
f(9,0,0);
dfs(9,0,0,0);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |