Submission #129813

#TimeUsernameProblemLanguageResultExecution timeMemory
129813pzdbaLjetopica (COI19_ljetopica)C++14
0 / 100
53 ms31864 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9+7; char s[1002], a[1002], b[1002]; ll dp[1002][1002][2], cnt[1002][1002][2]; int n, k; int dfs(char *s){ if(s[1] == '0') return 0; int res = 0; memset(dp, 0, sizeof(dp)); memset(cnt, 0, sizeof(cnt)); dp[1][0][0] = 1; cnt[1][0][0] = 1; dp[1][0][1] = 1; cnt[1][0][1] = 1; for(int i=2;i<=n;i++){ for(int j=0;j<=k;j++){ if(s[i] == 'L'){ dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][0]*2)%mod; cnt[i][j][0] = (cnt[i][j][0] + cnt[i][j][0] + cnt[i-1][j][0])%mod; dp[i][j][1] = (dp[i][j][1] + dp[i-1][j][1]*2 + cnt[i-1][j][1])%mod; cnt[i][j][1] = (cnt[i][j][1] + cnt[i][j][1] + cnt[i-1][j][1])%mod; if(j != k){ dp[i][j+1][1] = (dp[i][j+1][1] + dp[i-1][j][0]*2 + cnt[i-1][j][0])%mod; cnt[i][j+1][1] = (cnt[i][j+1][1] + cnt[i-1][j][0])%mod; dp[i][j+1][0] = (dp[i][j+1][0] + dp[i-1][j][1]*2)%mod; cnt[i][j+1][0] = (cnt[i][j+1][0] + cnt[i-1][j][1])%mod; } } else{ dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][0]*2 + cnt[i-1][j][0])%mod; cnt[i][j][0] = (cnt[i][j][0] + cnt[i][j][0] + cnt[i-1][j][0])%mod; dp[i][j][1] = (dp[i][j][1] + dp[i-1][j][1]*2)%mod; cnt[i][j][1] = (cnt[i][j][1] + cnt[i][j][1] + cnt[i-1][j][1])%mod; if(j != k){ dp[i][j+1][1] = (dp[i][j+1][1] + dp[i-1][j][0]*2)%mod; cnt[i][j+1][1] = (cnt[i][j+1][1] + cnt[i-1][j][0])%mod; dp[i][j+1][0] = (dp[i][j+1][0] + dp[i-1][j][1]*2 + cnt[i-1][j][1])%mod; cnt[i][j+1][0] = (cnt[i][j+1][0] + cnt[i-1][j][1])%mod; } } } } return (dp[n][k][0] + dp[n][k][1])%mod; } int main(){ scanf("%d%d", &n, &k); scanf("%s", s+2); scanf("%s", a+1); scanf("%s", b+1); for(int i=n;i>=1;i--){ if(a[i] == '1'){ a[i] = '0'; for(int j=i+1;j<=n;j++) a[j] = '1'; break; } } int res1 = dfs(a); int res2 = dfs(b); res2 = 0; printf("%d\n", (res1 - res2 + mod)%mod); }

Compilation message (stderr)

ljetopica.cpp: In function 'int dfs(char*)':
ljetopica.cpp:11:9: warning: unused variable 'res' [-Wunused-variable]
     int res = 0;
         ^~~
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
ljetopica.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s+2);    
     ~~~~~^~~~~~~~~~~
ljetopica.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", a+1);
     ~~~~~^~~~~~~~~~~
ljetopica.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", b+1);
     ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...