結果
問題 | No.611 Day of the Mountain |
ユーザー |
|
提出日時 | 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); | ~~~~~^~~~~~~~~~~~~
ソースコード
#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; }