結果

問題 No.611 Day of the Mountain
ユーザー Sebastian King
提出日時 2017-12-11 01:14:52
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,397 bytes
コンパイル時間 1,338 ms
コンパイル使用メモリ 159,616 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2024-11-30 11:31:25
合計ジャッジ時間 3,629 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 RE * 2
other AC * 2 WA * 2 RE * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘ll upd(ll&, ll)’:
main.cpp:31:1: warning: no return statement in function returning non-void [-Wreturn-type]
   31 | }
      | ^
main.cpp: In function ‘void solve(int)’:
main.cpp:58:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘ll’ {aka ‘long long int’} [-Wformat=]
   58 |         printf("%d\n", d[n][m]);
      |                 ~^     ~~~~~~~
      |                  |           |
      |                  int         ll {aka long long int}
      |                 %lld
main.cpp:35:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:37:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |                 scanf("%s", s + 1);
      |                 ~~~~~^~~~~~~~~~~~~

ソースコード

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MM = 201712111;
const double eps = 1e-8;
const int MAXN = 2000 + 10;
int n, m;
void prework(){
}
void read(){
}
int a[MAXN][MAXN];
ll d[MAXN][MAXN];
const ll INF = 1ll << 60;
char s[MAXN];
ll f[20][131072];
ll upd(ll &x, ll y){
    x = (x + y) % MM;
}
void solve(int casi){
//  cout << "Case #" << casi << ": ";
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++){
        scanf("%s", s + 1);
        for (int j = 1; j <= m; j++)
            a[i][j] = ((s[j] == '?') ? 0 : (s[j] - '0'));
    }
    if (m >= 18){
        // m > n
        for (int i = 1; i <= m; i++)
            for (int j = i + 1; j <= m; j++)
                swap(a[i][j], a[j][i]);
        swap(n, m);
    }
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            d[i][j] = INF;
    d[1][1] = (a[1][1] == 0) + a[1][1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            if (i != 1 || j != 1){
                d[i][j] = min(d[i-1][j], d[i][j-1]) + a[i][j] + (a[i][j] == 0);
            }
        }
    printf("%d\n", d[n][m]);
    if (m == 1){
        puts("1");
        return ;
    }
    int o = 1 << m;
    for (int i = 0; i < o; i++)
        f[1][i] = 0;
    f[1][1] = 1;
    int oo = o - 1;
    for (int cnt = 2; cnt <= n * m; cnt++){
        int x = (cnt - 1) / m + 1;
        int y = (cnt - 1) % m + 1;
        int py = (y == 1 ? m : y - 1);
        for (int i = 0; i < o; i++){
            f[y][i] = 0;
            //for (int j = 0; j < m; j++)
            //  f[y][i][j] = 0;
        }
        //cout << cnt << ' ' << x << ' ' << y << ' ' << py << endl;
        if (y == 1){
            if (a[x][y] == 0){
                for (int i = 0; i < o; i++){
                    if ((d[x-1][y]+1==d[x][y] && ((i >> (y - 1)) & 1))){
                        upd(f[y][i|(1<<(y-1))], f[py][i]);
                        upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]*8);
                    }
                    else{
                        upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]*9);
                    }
                }
            }
            else{
                for (int i = 0; i < o; i++){
                    if ((d[x-1][y]+a[x][y]==d[x][y] && ((i >> (y - 1)) & 1))){
                        upd(f[y][i|(1<<(y-1))], f[py][i]);
                    }
                    else{
                        upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]);
                    }
                }
            }
        }
        else{
            if (a[x][y] == 0){
                for (int i = 0; i < o; i++){
                    if ((d[x-1][y]+1==d[x][y] && ((i >> (y - 1)) & 1)) || (d[x][y-1]+1==d[x][y] && ((i >> (y - 2)) & 1))){
                        upd(f[y][i|(1<<(y-1))], f[py][i]);
                        upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]*8);
                        /*
                        for (int j = 0; j < m; j++){
                            if (j != y - 1){
                                upd(f[y][i][j], f[py][i][j]);
                                upd(f[y][i^(1<<(y-1))], f[py][i][j]*8);
                            }
                        }
                        upd(f[y][i][y-1], f[py][i][y-1] + f[py][i][y-2]);
                        upd(f[y][i^(1<<(y-1))], )*/
                    }
                    else{
                        upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]*9);
                    }
                }
            }
            else{
                for (int i = 0; i < o; i++){
                    if ((d[x-1][y]+a[x][y]==d[x][y] && ((i >> (y - 1)) & 1)) || (d[x][y-1]+a[x][y]==d[x][y] && ((i >> (y - 2)) & 1))){
                        upd(f[y][i|(1<<(y-1))], f[py][i]);
                        //upd(f[y][i&(o^(1<<(y-1)))], f[py][i]*8);
                    }
                    else{
                        upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]);
                    }
                }
            }
        }
        //for (int i = 0; i < o; i++)
        //  cout << f[y][i] << ' '; cout << endl;
    }
    
    //for (int i = 0; i < o; i++)
    //  cout << f[m][i] << ' '; cout << endl;
    
    ll ans = 0;
    for (int i = 0; i < o; i++)
        if ((i >> (m - 1)))
            upd(ans, f[m][i]);
    printf("%lld\n", ans);
}
void printans(){
}
int main(){
//  std::ios::sync_with_stdio(false);
    prework();
    int T = 1;
//  cin>>T;
    for(int i = 1; i <= T; i++){
        read();
        solve(i);
        printans();
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0