# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
611648 |
2022-07-29T06:17:05 Z |
반딧불(#8497) |
Ljetopica (COI19_ljetopica) |
C++17 |
|
500 ms |
18596 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
int n, k;
bool dir[1002];
ll comb[1002][1002]; /// comb[i][j] : iCj
ll pow2[1002];
ll DP[1002][1002][2]; /// DP[i][j][b]: ���� ���� i�� ��忡 �ְ�, �¿츦 j�� �ٲ� �� �ְ�, (k=1�̸� ���� �¿츦 �ݴ�� ���� ��) ���� ��
bool A[1002], B[1002];
ll ans;
inline void addAns(ll x){
ans = (ans + x) % MOD;
}
void dfs(int depth, int chance, bool following, ll offset, bool isBiggerThanA, bool isSmallerThanB){
if(chance < 0) return;
if(depth==n){
if(!chance) addAns(offset+1);
return;
}
if(isBiggerThanA && isSmallerThanB){ /// �ܼ� ����� ������ ���̽�
addAns(DP[depth][chance][following] + comb[n-depth][chance] * offset);
}
if(!(!isBiggerThanA && A[depth] == 1)){ /// �������� ���� ���� ���̴�
bool toFollow = !dir[depth];
dfs(depth+1, chance - (following ^ toFollow), toFollow, (offset+pow2[n-depth-1])%MOD, isBiggerThanA, (B[depth] == 1) || isSmallerThanB);
}
if(!(!isSmallerThanB && B[depth] == 0)){ /// ���������� ���� ���� ���̴�
bool toFollow = dir[depth];
dfs(depth+1, chance - (following ^ toFollow), toFollow, (offset+pow2[n-depth])%MOD, (A[depth] == 0 || isBiggerThanA), isSmallerThanB);
}
}
int main(){
for(int i=0; i<=1000; i++){
comb[i][0] = comb[i][i] = 1;
for(int j=1; j<i; j++) comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;
}
pow2[0] = 1;
for(int i=1; i<=1000; i++) pow2[i] = pow2[i-1] * 2 % MOD;
scanf("%d %d", &n, &k);
for(int i=1; i<n; i++){
char c;
scanf(" %c", &c);
dir[i] = (c == 'R');
}
DP[n][0][0] = DP[n][0][1] = 1;
for(int d=n-1; d>=1; d--){ /// ���� ����
for(int j=0; j<=n-d; j++){
ll cntNo = comb[n-d-1][j], cntYes = j ? comb[n-d-1][j-1] : 0;
DP[d][j][0] += (DP[d+1][j][0] + (!dir[d] ? pow2[n-d-1] : pow2[n-d]) * cntNo);
if(j) DP[d][j][0] += (DP[d+1][j-1][1] + (dir[d] ? pow2[n-d-1] : pow2[n-d]) * cntYes);
DP[d][j][0] %= MOD;
if(j) DP[d][j][1] += (DP[d+1][j-1][0] + (!dir[d] ? pow2[n-d-1] : pow2[n-d]) * cntYes);
DP[d][j][1] += (DP[d+1][j][1] + (dir[d] ? pow2[n-d-1] : pow2[n-d]) * cntNo);
DP[d][j][1] %= MOD;
// printf("(%d %d): (%lld %lld)\n", d, j, DP[d][j][0], DP[d][j][1]);
}
}
for(int i=0; i<n; i++) scanf("%1d", &A[i]);
for(int i=0; i<n; i++) scanf("%1d", &B[i]);
for(int i=0; i<n; i++){
if(A[i] < B[i]) break;
if(A[i] > B[i]){
puts("0");
return 0;
}
}
dfs(1, k, 0, 0, 0, 0);
dfs(1, k, 1, 0, 0, 0);
printf("%lld", ans);
}
Compilation message
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:71:37: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'bool*' [-Wformat=]
71 | for(int i=0; i<n; i++) scanf("%1d", &A[i]);
| ~~^ ~~~~~
| | |
| | bool*
| int*
ljetopica.cpp:72:37: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'bool*' [-Wformat=]
72 | for(int i=0; i<n; i++) scanf("%1d", &B[i]);
| ~~^ ~~~~~
| | |
| | bool*
| int*
ljetopica.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
ljetopica.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
ljetopica.cpp:71:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | for(int i=0; i<n; i++) scanf("%1d", &A[i]);
| ~~~~~^~~~~~~~~~~~~~
ljetopica.cpp:72:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | for(int i=0; i<n; i++) scanf("%1d", &B[i]);
| ~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
18516 KB |
Output is correct |
2 |
Correct |
16 ms |
17748 KB |
Output is correct |
3 |
Correct |
14 ms |
17008 KB |
Output is correct |
4 |
Correct |
15 ms |
16096 KB |
Output is correct |
5 |
Correct |
10 ms |
15348 KB |
Output is correct |
6 |
Correct |
10 ms |
14556 KB |
Output is correct |
7 |
Correct |
9 ms |
13880 KB |
Output is correct |
8 |
Correct |
9 ms |
13112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
7252 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1071 ms |
18596 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
18516 KB |
Output is correct |
2 |
Correct |
16 ms |
17748 KB |
Output is correct |
3 |
Correct |
14 ms |
17008 KB |
Output is correct |
4 |
Correct |
15 ms |
16096 KB |
Output is correct |
5 |
Correct |
10 ms |
15348 KB |
Output is correct |
6 |
Correct |
10 ms |
14556 KB |
Output is correct |
7 |
Correct |
9 ms |
13880 KB |
Output is correct |
8 |
Correct |
9 ms |
13112 KB |
Output is correct |
9 |
Incorrect |
19 ms |
7252 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |