Submission #156235

#	Time	Username	Problem	Language	Result	Execution time	Memory
156235		mdn2002	Jetpack (COCI16_jetpack)	C++14	80 / 80	169 ms	15068 KiB

jetpack

#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);
            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)

jetpack.cpp: In function 'void dfs(int, int, int, int)':
jetpack.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<a.size();i++)cout<<a[i]<<' '<<b[i]<<endl;
                     ~^~~~~~~~~

• Subtask 1: 80 / 80