結果

問題 No.611 Day of the Mountain
ユーザー heyshbheyshb
提出日時 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);
      |                 ~~~~~^~~~~~~~~~~~

ソースコード

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

#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;
else
v[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;
else
res = v1;
}
else
{
if (U[i][j])
res = v1;
else
res = 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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0