結果
問題 | No.611 Day of the Mountain |
ユーザー |
|
提出日時 | 2017-12-11 22:46:42 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 212 ms / 2,017 ms |
コード長 | 2,965 bytes |
コンパイル時間 | 1,369 ms |
コンパイル使用メモリ | 162,780 KB |
実行使用メモリ | 46,720 KB |
最終ジャッジ日時 | 2024-11-30 21:06:14 |
合計ジャッジ時間 | 3,034 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:175:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘LL’ {aka ‘long long int’} [-Wformat=] 175 | printf("%d\n",ans); | ~^ ~~~ | | | | int LL {aka long long int} | %lld main.cpp:25:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 25 | scanf("%d%d",&N,&M); | ~~~~~^~~~~~~~~~~~~~ main.cpp:28:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 28 | scanf("%s",s + 1); | ~~~~~^~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long LL;int N,M;LL v[1210][1210];char s[1210];const LL MOD = 201712111;int f0[1210][20];LL f[2][20][1<<17];bool L[1210][20],U[1210][20];inline int gg(int x){return x==-1?1:x;}void upd(LL &x){//if (x >= MOD) x-= MOD;x %= MOD;}int main(){//freopen("611.in","r",stdin);scanf("%d%d",&N,&M);for (int i=1;i<=N;i++){scanf("%s",s + 1);for (int j=1;j<=M;j++)if (s[j] == '?')v[i][j] = -1;elsev[i][j] = s[j] - '0';}if (N < M){for (int i=1;i<=M;i++)for (int j=1;j<=i;j++)swap(v[i][j],v[j][i]);swap(N,M);}/*printf("%d %d\n",N,M);for (int i=1;i<=N;i++){for (int j=1;j<=M;j++)printf("%d ",v[i][j]);puts("");}puts("");*/assert(M <= 17);memset(f0,60,sizeof(f0));f0[1][1] = gg(v[1][1]);for (int i=1;i<=N;i++)for (int j=1;j<=M;j++){if (i>1) f0[i][j] = min(f0[i][j],f0[i-1][j] + gg(v[i][j]));if (j>1) f0[i][j] = min(f0[i][j],f0[i][j-1] + gg(v[i][j]));}printf("%d\n",f0[N][M]);for (int i=1;i<=N;i++){for (int j=1;j<=M;j++){L[i][j] = (f0[i][j] == f0[i][j-1] + gg(v[i][j]));U[i][j] = (f0[i][j] == f0[i-1][j] + gg(v[i][j]));//printf("%d",U[i][j]);}}int up = (1 << M);LL ans = 0;memset(f,0,sizeof(f));f[0][M][1] = 1;U[1][1] = true;int now = 1,last = 0;for (int i=1;i<=N;i++){for (int k=0;k<up;k++){f[now][1][k] = 0;if (k & 1){f[now][1][k] = f[last][M][k];}else{if (v[i][1] == -1){f[now][1][k] = f[last][M][k & (~1)] * 9 + f[last][M][k | 1] * 8;}else{f[now][1][k] = f[last][M][k & (~1)];}upd(f[now][1][k]);}}for (int j=2;j<=M;j++)for (int k=0;k<up;k++){LL &res = f[now][j][k];res = 0;if (k & (1 << (j - 1))){LL v1 = f[now][j-1][k], v2 = f[now][j-1][k ^ (1 << (j - 1))];if (k & (1 << (j - 2))){if (L[i][j])res = v1 + v2;elseres = v1;}else{if (U[i][j])res = v1;elseres = 0;}upd(res);}else{LL v1 = f[now][j-1][k], v2 = f[now][j-1][k ^ (1 << (j - 1))];LL b = (v[i][j] == -1)?9:1;if (k & (1 << (j - 2))){if (L[i][j]){res = (v1 + v2) % MOD * (b - 1);}else{res = v1 * b % MOD + v2 * (b - 1) % MOD;}}else{if (U[i][j]){res = v1 * b % MOD + v2 * (b - 1) % MOD;}else{res = (v1 + v2) % MOD * b;}}upd(res);}}/*for (int j=1;j<=M;j++)for (int k=0;k<up;k++){printf("f[%d][%d][",i,j);print(k);printf("] = %d\n",f[now][j][k]);}*/if (i == N)for (int k=0;k<up;k++)if (k & (1 << (M - 1))){ans = ans + f[now][M][k];upd(ans);}now ^= 1;last ^= 1;}printf("%d\n",ans);}