oj.uz

Submission #144124

# Submission time Handle Problem Language Result Execution time Memory
144124 2019-08-16T07:11:40 Z Abelyan Ljetopica (COI19_ljetopica) C++17
22 / 100
 385 ms 80576 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=2e3+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;

ll dp[N][N][2][2][2],qan[N][N][2][2][2],P[N];
int s[N],a[N],b[N],qan0,qan1;
bool col0,col1;
char tv;


int main(){
    fastio;
    srng;
    int n,k;
    cin>>n>>k;
    n--;
    FOR(i,n){
        char c;
        cin>>c;
        if (c=='L')s[i]=0;
        else s[i]=1;

    }
    FOR(i,2*n){
        if (!i)P[i]=1;
        else P[i]=(P[i-1]*2ll)%MOD;
    }
    cin>>tv;
    if (tv==0)assert(0);
    FOR(i,n){
        char c;
        cin>>c;
        a[i]=c-'0';
        if (tv=='0')a[i]=0;
    }
    cin>>tv;
    if (tv=='0'){
        assert(0);
        cout<<0<<endl;
        return 0;
    }
    FOR(i,n){
        char c;
        cin>>c;
        b[i]=c-'0';
    }
    FOR(pla,2)FOR(plb,2)FOR(hak,2)qan[n][0][pla][plb][hak]=1;
    //cout<<n<<endl;
    FORD(i,n){
        //cout<<i<<endl;
        FOR(j,k+1){
            //if (n-i<j)continue;
            //cout<<1<<endl;
            FOR(pla,2){
                FOR(plb,2){
                    FOR(hak,2){
                        if (hak)s[i]=1-s[i];
                        qan0=0;
                        qan1=0;
                        col0=true;
                        col1=true;
                        if ((pla && a[i]) || (!j && s[i])){
                            col0=false;
                        }
                        if ((plb && !b[i]) || (!j && !s[i])){
                            col1=false;
                        }
                        //cout<<pla<<" "<<plb<<" "<<i<<" "<<col0<<" "<<col1<<endl;
                        if (s[i]==0)qan1=1;
                        if (s[i]==1)qan0=1;
                        int la1=pla;
                        if (a[i]==0)la1=0;
                        int lb0=plb;
                        if (b[i]==1)lb0=0;
                        if (col0){
                            int pox=(hak+qan0)%2;
                            dp[i][j][pla][plb][hak]+=dp[i+1][j-qan0][pla][lb0][pox];
                            dp[i][j][pla][plb][hak]%=MOD;
                            qan[i][j][pla][plb][hak]+=qan[i+1][j-qan0][pla][lb0][pox];
                        }
                        if (col1){
                            int pox=(hak+qan1)%2;
                            /*
                            if (hak && !i && pla==plb && pla){
                                cout<<la1<<endl;
                            }*/
                            dp[i][j][pla][plb][hak]+=(dp[i+1][j-qan1][la1][plb][pox]+(qan[i+1][j-qan1][la1][plb][pox]*P[n-i-1])%MOD)%MOD;
                            dp[i][j][pla][plb][hak]%=MOD;
                            qan[i][j][pla][plb][hak]+=qan[i+1][j-qan1][la1][plb][pox];
                        }
                        if (hak)s[i]=1-s[i];
                        //if (hak)
                            //cout<<i<<" "<<pla<<" "<<plb<<" "<<dp[i][j][pla][plb][hak]<<" "<<qan[i][j][pla][plb][hak]<<" "<<col0<<" "<<col1<<endl;
                    }
                }
            }
        }
    }

    //cout<<dp[0][k][1][1]<<endl;
    dp[0][k][1][1][0]+=(qan[0][k][1][1][0]*P[n])%MOD;
    dp[0][k][1][1][0]%=MOD;
    dp[0][k][1][1][1]+=(qan[0][k][1][1][1]*P[n])%MOD;
    dp[0][k][1][1][1]%=MOD;
    //cout<<qan[0][k][1][1]<<endl;

    cout<<(dp[0][k][1][1][1]+dp[0][k][1][1][0])%MOD<<endl;
    return 0;
}
/*
7 2 8
C 1
C 2
C 3
C 4
C 5
C 6
O 7
O 7

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8824 KB Output is correct
2 Correct 9 ms 8440 KB Output is correct
3 Correct 9 ms 8056 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 9 ms 7288 KB Output is correct
6 Correct 8 ms 6776 KB Output is correct
7 Correct 8 ms 6392 KB Output is correct
8 Correct 7 ms 5880 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 632 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 2 ms 632 KB Output is correct
15 Correct 2 ms 632 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 385 ms 80576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8824 KB Output is correct
2 Correct 9 ms 8440 KB Output is correct
3 Correct 9 ms 8056 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 9 ms 7288 KB Output is correct
6 Correct 8 ms 6776 KB Output is correct
7 Correct 8 ms 6392 KB Output is correct
8 Correct 7 ms 5880 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 636 KB Output is correct
13 Correct 2 ms 508 KB Output is correct
14 Correct 2 ms 632 KB Output is correct
15 Correct 2 ms 632 KB Output is correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 2 ms 504 KB Output is correct
20 Correct 2 ms 632 KB Output is correct
21 Correct 2 ms 632 KB Output is correct
22 Correct 2 ms 632 KB Output is correct
23 Correct 2 ms 632 KB Output is correct
24 Incorrect 385 ms 80576 KB Output isn't correct
25 Halted 0 ms 0 KB -