結果
問題 | No.611 Day of the Mountain |
ユーザー |
|
提出日時 | 2023-12-02 17:59:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 265 ms / 2,017 ms |
コード長 | 1,444 bytes |
コンパイル時間 | 1,925 ms |
コンパイル使用メモリ | 195,688 KB |
最終ジャッジ日時 | 2025-02-18 06:03:19 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:15:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 15 | scanf("%d%d",&n,&m); | ~~~~~^~~~~~~~~~~~~~ main.cpp:17:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 17 | scanf("%s",s+1); | ~~~~~^~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MM=201712111; const int MAXN=2000+10; int n,m; int a[MAXN][MAXN]; ll d[MAXN][MAXN],ans,f[20][131072]; const ll INF=1ll << 60; char s[MAXN]; void upd(ll &x,ll y){x=(x+y)%MM;} int main(){ 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){ 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("%lld\n",d[n][m]); if (m==1) return 0*puts("1"); int o=1 << m; for (int i=0;i<o;i++) f[1][i]=(i==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; if (a[x][y]==0){ for (int i=0;i<o;i++) if(f[py][i]) upd(f[y][i&(oo^(1<<(y-1)))],f[py][i]*8); a[x][y]=1; } for (int i=0;i<o;i++) if(f[py][i]) if ((d[x-1][y]+a[x][y]==d[x][y]&&((i>>(y-1))&1))||(y>=2&&d[x][y-1]+a[x][y]==d[x][y]&&((i>>(y-2))&1))) upd(f[y][i|(1<<(y-1))],f[py][i]); else upd(f[y][i&(oo^(1<<(y-1)))],f[py][i]); } for (int i=0;i<o;i++) if ((i>>(m-1))) upd(ans,f[m][i]); printf("%lld\n",ans); return 0; }