oj.uz

답안 #156235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
156235 2019-10-04T15:53:01 Z mdn2002 Jetpack (COCI16_jetpack) C++14
80 / 80
 169 ms 15068 KB 
#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

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.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5884 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 8 ms 5880 KB Output is correct
5 Correct 14 ms 6264 KB Output is correct
6 Correct 16 ms 6392 KB Output is correct
7 Correct 34 ms 7544 KB Output is correct
8 Correct 77 ms 10104 KB Output is correct
9 Correct 112 ms 12268 KB Output is correct
10 Correct 169 ms 15068 KB Output is correct