Submission #715453

#	Time	Username	Problem	Language	Result	Execution time	Memory
715453		Ahmed57	Ljetopica (COI19_ljetopica)	C++14	100 / 100	95 ms	63232 KiB

ljetopica

#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|L|R
//||R|L|R
//|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)%mod+sum.second)%mod<<endl;
}

Compilation message (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 17 / 17
• Subtask 4: 61 / 61