結果

問題 No.611 Day of the Mountain
ユーザー WA_TLE
提出日時 2017-12-11 01:48:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 350 ms / 2,017 ms
コード長 3,385 bytes
コンパイル時間 1,582 ms
コンパイル使用メモリ 136,448 KB
最終ジャッジ日時 2025-01-05 05:08:06
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=201712111;
const llint big=1e15+100;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
int main(void){
    int i,j,h,w,bi;cin>>h>>w;
    vector<string>kyuri(h);//山なので
    for(i=0;i<h;i++){cin>>kyuri[i];}
    if(h<w){
        vector<string>ne(w);//ぬえっ!
        for(i=0;i<w;i++){ne[i].res(h);}
        for(i=0;i<h;i++){
            for(j=0;j<w;j++){
                ne[j][i]=kyuri[i][j];
            }
        }
        swap(h,w);
        swap(kyuri,ne);
    }
    //w>hになったw<=18
    //bitDPPPPPPPPP
    vector<vector<int>>time(h);
    for(i=0;i<h;i++){
        time[i].res(w);
        for(j=0;j<w;j++){
            if(i==0&&j==0){time[i][j]=0;}//(0ではない)
            else if(i==0){time[i][j]=time[i][j-1];}
            else if(j==0){time[i][j]=time[i-1][j];}
            else{time[i][j]=min(time[i][j-1],time[i-1][j]);}
            if(kyuri[i][j]=='?'){time[i][j]++;}
            else{time[i][j]+=kyuri[i][j]-'0';}
        }
    }
    
    int T=time[h-1][w-1];
    cout<<T<<endl;
    vector<vector<int>>Rtime(h);
    for(i=h-1;i>=0;i--){
        Rtime[i].res(w);
        for(j=w-1;j>=0;j--){
            if(i==h-1&&j==w-1){Rtime[i][j]=0;}
            else if(i==h-1){Rtime[i][j]=Rtime[i][j+1];}
            else if(j==w-1){Rtime[i][j]=Rtime[i+1][j];}
            else{Rtime[i][j]=min(Rtime[i][j+1],Rtime[i+1][j]);}
            if(kyuri[i][j]=='?'){Rtime[i][j]++;}
            else{Rtime[i][j]+=kyuri[i][j]-'0';}
        }
    }
    vector<vector<int>>just(h);
    for(i=0;i<h;i++){
        just[i].res(w);
        for(j=0;j<w;j++){
            int kor;
            if(kyuri[i][j]=='?'){kor=1;}
            else{kor=kyuri[i][j]-'0';}
            if(Rtime[i][j]+time[i][j]==T+kor){just[i][j]=1;}
            else{just[i][j]=0;}
        }
    }
    vector<llint>bdp(1<<w);
    bdp[1]=1;
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            if(i==0&&j==0){continue;}
            vector<llint>ndp(1<<w);
            int bji=(1<<j);
            int kor;if(kyuri[i][j]=='?'){kor=1;}else{kor=kyuri[i][j]-'0';}
            bool uecan=(i!=0&&time[i-1][j]+kor==time[i][j]&&just[i][j]==1);
            bool yocan=(j!=0&&time[i][j-1]+kor==time[i][j]&&just[i][j]==1);
            
            for(bi=0;bi<(1<<w);bi++){
                bool uearu=uecan&&((bi&bji)!=0);
                bool yoaru=yocan&&((bi&(bji/2))!=0);
                if(uearu||yoaru){ndp[bi|bji]+=bdp[bi];}
                else{ndp[bi-(bi&bji)]+=bdp[bi];}
                if(kyuri[i][j]=='?'){ndp[bi-(bi&bji)]+=bdp[bi]*8;}
            }
            for(bi=0;bi<(1<<w);bi++){ndp[bi]%=mod;}
            bdp=move(ndp);
        }
    }
    llint ans=0;
    for(bi=(1<<(w-1));bi<(1<<w);bi++){ans+=bdp[bi];ans%=mod;}
    cout<<ans<<endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0