oj.uz

Submission #611832

# Submission time Handle Problem Language Result Execution time Memory
611832 2022-07-29T08:00:40 Z 조영욱(#8499) Ljetopica (COI19_ljetopica) C++17
25 / 100
 43 ms 31812 KB 
#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
typedef pair<long long,long long> P;
P dp[1001][1001][2]; //dp[i][j]:i��°���� �����ϰ� j�� ������ �ٲٰ� �������� j=0:���� j=1:�ٸ� �̾���
char str[1001];
int n,k;
long long fp[1001];

P ans(int ind,int x,int t) {
    if (dp[ind][x][t].first!=-1) {
        return dp[ind][x][t];
    }
    if (ind==n) {
        return dp[ind][x][t]=(x==0?P(1,0):P(0,0));
    }
    P ret=P(0,0);
    if (x>0) {
        int dir=0;
        if (str[ind]=='L') {
            dir=0;
        }
        else {
            dir=1;
        }
        if (t==0) {
            dir^=1;
        }
        P got=ans(ind+1,x-1,1-t);
        if (dir==1) {
            got.second+=fp[n-ind-1]*got.first;
            got.second%=mod;
        }
        ret.first+=got.first;
        ret.second+=got.second;
    }
    int dir=0;
    if (str[ind]=='L') {
        dir=0;
    }
    else {
        dir=1;
    }
    if (t==1) {
        dir^=1;
    }
    P got=ans(ind+1,x,t);
    if (dir==1) {
        got.second+=fp[n-ind-1]*got.first;
        got.second%=mod;
    }
    ret.first+=got.first;
    ret.second+=got.second;
    ret.first%=mod;
    ret.second%=mod;
    return dp[ind][x][t]=ret;
}

int a[1000];
int b[1000];

P pl(P a,P b) {
    return P((a.first+b.first)%mod,(a.second+b.second)%mod);
}

P fa(int t,int ind=1,int x=k) {
    P ret=P(0,0);
    if (ind==n) {
        return x==0?P(1,0):P(0,0);
    }
    if (ind!=1) {
        int pr=0;
        if (str[ind-1]=='R') {
            pr=1;
        }
        if (t) {
            pr^=1;
        }
        if (a[ind-1]<pr) {
            return ans(ind,x,t);
        }
        if (a[ind-1]>pr) {
            return P(0,0);
        }
    }
    int dir=0;
    if (str[ind]=='R') {
        dir=1;
    }
    if (t) {
        dir^=1;
    }
    if (x>0) {
        P got=fa(1-t,ind+1,x-1);
        if (dir==0) {
            got.second+=got.first*fp[n-ind-1];
        }
        ret=pl(ret,got);
    }
    P got=fa(t,ind+1,x);
    if (dir==1) {
        got.second+=got.first*fp[n-ind-1];
    }
    ret=pl(ret,got);
    return ret;
}

P fb(int t,int ind=1,int x=k) {
    P ret=P(0,0);
    if (ind!=1) {
        int pr=0;
        if (str[ind-1]=='R') {
            pr=1;
        }
        if (t) {
            pr^=1;
        }
        if (b[ind-1]>pr) {
            return ans(ind,x,t);
        }
        if (b[ind-1]<pr) {
            return P(0,0);
        }
    }
    if (ind==n) {
        return x==0?P(1,0):P(0,0);
    }
    int dir=0;
    if (str[ind]=='R') {
        dir=1;
    }
    if (t) {
        dir^=1;
    }
    if (x>0) {
        P got=fb(1-t,ind+1,x-1);
        if (dir==0) {
            got.second+=got.first*fp[n-ind-1];
        }
        ret=pl(ret,got);
    }
    P got=fb(t,ind+1,x);
    if (dir==1) {
        got.second+=got.first*fp[n-ind-1];
    }
    ret=pl(ret,got);
    return ret;
}

long long f(P x) {
    long long ret=x.second;
    ret+=fp[n-1]*x.first;
    return ret%mod;
}

int main(void) {
    scanf("%d %d",&n,&k);
    scanf("%s",str+1);
    fp[0]=1;
    for(int i=1;i<=n;i++) {
        fp[i]=(fp[i-1]*2)%mod;
    }
    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++) {
        for(int j=0;j<=n;j++) {
            dp[i][j][0]=P(-1,-1);
            dp[i][j][1]=P(-1,-1);
        }
    }
    long long ret=f(fa(0));
    ret+=f(fa(1));
    ret+=f(fb(0));
    ret+=f(fb(1));
    ret%=mod;
    ret+=mod-f(ans(1,k,0));
    ret+=mod-f(ans(1,k,1));
    ret%=mod;
    printf("%lld",ret);
}

Compilation message

ljetopica.cpp: In function 'int main()':
ljetopica.cpp:158:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
ljetopica.cpp:159:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |     scanf("%s",str+1);
      |     ~~~~~^~~~~~~~~~~~
ljetopica.cpp:165:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         scanf("%1d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~
ljetopica.cpp:168:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         scanf("%1d",&b[i]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31772 KB Output is correct
2 Correct 15 ms 30104 KB Output is correct
3 Correct 14 ms 28612 KB Output is correct
4 Correct 13 ms 26372 KB Output is correct
5 Correct 13 ms 23656 KB Output is correct
6 Correct 9 ms 20948 KB Output is correct
7 Correct 10 ms 18516 KB Output is correct
8 Correct 8 ms 16216 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 440 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 432 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 31700 KB Output is correct
2 Correct 31 ms 31776 KB Output is correct
3 Correct 30 ms 31776 KB Output is correct
4 Correct 37 ms 31776 KB Output is correct
5 Correct 28 ms 31768 KB Output is correct
6 Correct 41 ms 31812 KB Output is correct
7 Correct 25 ms 31748 KB Output is correct
8 Correct 37 ms 31728 KB Output is correct
9 Correct 15 ms 31708 KB Output is correct
10 Correct 32 ms 31780 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31772 KB Output is correct
2 Correct 15 ms 30104 KB Output is correct
3 Correct 14 ms 28612 KB Output is correct
4 Correct 13 ms 26372 KB Output is correct
5 Correct 13 ms 23656 KB Output is correct
6 Correct 9 ms 20948 KB Output is correct
7 Correct 10 ms 18516 KB Output is correct
8 Correct 8 ms 16216 KB Output is correct
9 Correct 1 ms 436 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 440 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 440 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 432 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Incorrect 1 ms 340 KB Output isn't correct
24 Halted 0 ms 0 KB -