oj.uz

Submission #715452

# Submission time Handle Problem Language Result Execution time Memory
715452 2023-03-26T19:34:40 Z Ahmed57 Ljetopica (COI19_ljetopica) C++14
0 / 100
 74 ms 40456 KB 
#include <bits/stdc++.h>

using namespace std;
pair<long long,long long> dp[1001][1001][2][2];
string l,r;
string mo;
int org = 0;
pair<long long,long long> neg = {-1,-1};
long long mod = int(1e9)+7;
long long pw[1001];
//1000
//1001
//1010
//1101
//1110
//1111
//|R|R|L 1110
//||LR|L 1010
//||L|LL 1000
//|RL|R 1101
//|R|RR 1111
//L|L|R 1001
pair<long long,long long> solve(int i,int rem,int lowe,int uppe){
    if(i==mo.size()){
        return {(rem==0?1:0),0};
    }
    if(dp[i][rem][lowe][uppe]!=neg)return dp[i][rem][lowe][uppe];
    int diff = (org-rem)%2;
    char st = '0';
    if(mo[i]=='R')st = '1';
    pair<long long,long long>all = {0,0};
    long long nu = 0;bool ss = 0;
    for(char j = st;j<=st;j++){
        char c = j;
        if(diff){
            if(c=='0')c = '1';
            else c = '0';
        }
        if(c=='1')ss = 1;
        if(c<r[i+1]){
            if(c>l[i+1]){
                all.first+=solve(i+1,rem,1,1).first;
                all.second+=solve(i+1,rem,1,1).second;
                all.first%=mod;
                all.second%=mod;
                if(ss)nu+=solve(i+1,rem,1,1).first;
                nu%=mod;
            }else if(c==l[i+1]||lowe){
                all.first+=solve(i+1,rem,lowe,1).first;
                all.second+=solve(i+1,rem,lowe,1).second;
                all.first%=mod;
                all.second%=mod;
                if(ss)nu+=solve(i+1,rem,lowe,1).first;
                nu%=mod;
            }
        }else if(c==r[i+1]||uppe){
            if(c>l[i+1]){
                all.first+=solve(i+1,rem,1,uppe).first;
                all.second+=solve(i+1,rem,1,uppe).second;
                all.first%=mod;
                all.second%=mod;
                if(ss)nu+=solve(i+1,rem,1,uppe).first;
                nu%=mod;
            }else if(c==l[i+1]||lowe){
                all.first+=solve(i+1,rem,lowe,uppe).first;
                all.second+=solve(i+1,rem,lowe,uppe).second;
                all.first%=mod;
                all.second%=mod;
                if(ss)nu+=solve(i+1,rem,lowe,uppe).first;
                nu%=mod;
            }
        }
    }
    int orginalRem = rem;
    if(rem>0){
        rem--;
        ss =0;
        diff = !diff;
        for(char j = st;j<=st;j++){
        char c = j;
        if(diff){
            if(c=='0')c = '1';
            else c = '0';
        }
        if(c=='1')ss=1;
        if(c<r[i+1]){
            if(c>l[i+1]){
                all.first+=solve(i+1,rem,1,1).first;
                all.second+=solve(i+1,rem,1,1).second;
                all.first%=mod;
                all.second%=mod;
                if(ss)nu+=solve(i+1,rem,1,1).first;
                nu%=mod;
            }else if(c==l[i+1]||lowe){
                all.first+=solve(i+1,rem,lowe,1).first;
                all.second+=solve(i+1,rem,lowe,1).second;
                all.first%=mod;
                all.second%=mod;
                if(ss)nu+=solve(i+1,rem,lowe,1).first;
                nu%=mod;
            }
        }else if(c==r[i+1]||uppe){
            if(c>l[i+1]){
                all.first+=solve(i+1,rem,1,uppe).first;
                all.second+=solve(i+1,rem,1,uppe).second;
                all.first%=mod;
                all.second%=mod;
                if(ss)nu+=solve(i+1,rem,1,uppe).first;
                nu%=mod;
            }else if(c==l[i+1]||lowe){
                all.first+=solve(i+1,rem,lowe,uppe).first;
                all.second+=solve(i+1,rem,lowe,uppe).second;
                all.first%=mod;
                all.second%=mod;
                if(ss)nu+=solve(i+1,rem,lowe,uppe).first;
                nu%=mod;
            }
        }
    }
    }
    all.second+=(nu*pw[(mo.size()-1)-i])%mod;
    all.second%=mod;
    return dp[i][orginalRem][lowe][uppe] =all;
}
signed main(){
    pw[0] = 1;
    for(int i = 1;i<=1000;i++){
        pw[i] = (pw[i-1]*2)%mod;
    }
    long long n,k;
    cin>>n>>k;
    org =k;
    cin>>mo>>l>>r;
    for(int i = 0;i<=n;i++){
        for(int j = 0;j<=k;j++){
            dp[i][j][0][0] = neg;
            dp[i][j][1][0] = neg;
            dp[i][j][1][1] = neg;
            dp[i][j][0][1] = neg;
        }
    }
    pair<long long,long long> sum = solve(0,k,0,0);
    //
    for(int i = 0;i<=n;i++){
        for(int j = 0;j<=k;j++){
            dp[i][j][0][0] = neg;
            dp[i][j][1][0] = neg;
            dp[i][j][1][1] = neg;
            dp[i][j][0][1] = neg;
        }
    }
    for(int i =0 ;i<mo.size();i++){
        if(mo[i]=='R')mo[i] ='L';
        else mo[i] = 'R';
    }
    sum.first+=solve(0,k,0,0).first;
    sum.second+=solve(0,k,0,0).second;
    cout<<pw[n-1]*sum.first+sum.second<<endl;
}

Compilation message

ljetopica.cpp: In function 'std::pair<long long int, long long int> solve(int, int, int, int)':
ljetopica.cpp:24:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if(i==mo.size()){
      |        ~^~~~~~~~~~~
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:152:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for(int i =0 ;i<mo.size();i++){
      |                   ~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Incorrect 2 ms 4308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Incorrect 2 ms 4308 KB Output isn't correct
3 Halted 0 ms 0 KB -