Submission #185625

#	Time	Username	Problem	Language	Result	Execution time	Memory
185625		anonymous	Ljetopica (COI19_ljetopica)	C++14	100 / 100	121 ms	63372 KiB

ljetopica

#include<iostream>
#define MAXN 1005
#define MOD 1000000007
#define LL long long
using namespace std;
int N, K;
char seq[MAXN], A[MAXN], B[MAXN];
LL pow2[MAXN];
LL dp[MAXN][MAXN][2][2], dp2[MAXN][MAXN][2][2]; //num, contribution
//n,k, invert, t
LL f(int n, int k, int i,  int t) {
    if (k < 0) {return(0);}
    return(dp[n][k][i][t]);
}

LL f2(int n, int k, int i, int t) {
    if (k < 0) {return(0);}
    return(dp2[n][k][i][t]);
}

int cost(int i, char At, char Do) {
    if (i) {return(At == Do);}
    return(At != Do);
}

LL slv(char* V) {
    dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][1][0]=dp[0][0][1][1]=1;
    for (int n=1; n<N; n++) {
        for (int k=0; k<=K; k++) {
          for (int i=0; i<=1; i++) {
            char L='L', R='R'; //R is the actual way to go right
            //if (i) {swap(L,R);}
            for (int t=0; t<=1; t++) {
                if (t == 0) {
                    //not tight
                    dp[n][k][i][t]=(f(n-1, k-1, not(i),  0)+f(n-1, k, i, 0))%MOD;
                    dp2[n][k][i][t]=(f2(n-1, k-1, not(i), 0)+f2(n-1, k, i, 0)+f(n-1, k-cost(i, seq[n], R), (seq[n] != R),  0)*pow2[n-1])%MOD;

                } else {
                    dp[n][k][i][t]=f(n-1, k-cost(i, seq[n], L), (seq[n] != L), V[n] == '0'); //choose 0
                    dp2[n][k][i][t]=f2(n-1, k-cost(i, seq[n], L), (seq[n] != L),  V[n] == '0'); //choose 0
                    //printf("%d %d %d %d %lld %lld %d\n", n,k,i,t, f(n-1, k-cost(i, seq[n], L), (seq[n] != L), V[n] == '0'), f(n,k, i, t), cost(i, seq[n], L));
                    if (V[n] == '1') {
                        dp[n][k][i][t]=(dp[n][k][i][t] + f(n-1, k-cost(i, seq[n], R),(seq[n] != R), 1))%MOD; //choose 1 so increase hamming weight if seq[n] = 'L'
                        dp2[n][k][i][t]=(dp2[n][k][i][t] + f2(n-1, k-cost(i, seq[n], R),  (seq[n] != R), 1) + f(n-1, k-cost(i, seq[n], R),  (seq[n] != R), 1)*pow2[n-1])%MOD;
                    }
                }
            }
          }
        }
    }
    //printf("%lld %lld\n", dp[N-1][K][0][1], dp[N-1][K][1][1]);
    return((dp2[N-1][K][0][1]+dp2[N-1][K][1][1] + (dp[N-1][K][0][1]+dp[N-1][K][1][1])*pow2[N-1])%MOD);
}

void initpow() {
    pow2[0]=1;
    for (int i=1; i<=N; i++) {
        pow2[i]=(2*pow2[i-1])%MOD;
    }
}
int main() {
    //freopen("ljin.txt","r",stdin);
    scanf("%d %d", &N, &K);
    for (int i=1; i<N; i++) {
        scanf("\n%c", &seq[N-i]);
    }
    for (int i=0; i<N; i++) {
        scanf("\n%c", &A[N-i]);
    }
    for (int i=0; i<N; i++) {
        scanf("\n%c", &B[N-i]);
    }
    initpow();

    LL ans=(slv(B)-slv(A)+MOD)%MOD;
    for (int i=1; i<=N; i++) {
        if (A[i] == '1') {
            ans=(ans+pow2[i-1])%MOD;
        }
    }
    printf("%lld", ans);
}

Compilation message (stderr)

ljetopica.cpp: In function 'int main()':
ljetopica.cpp:64: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:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c", &seq[N-i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~
ljetopica.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c", &A[N-i]);
         ~~~~~^~~~~~~~~~~~~~~~~
ljetopica.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c", &B[N-i]);
         ~~~~~^~~~~~~~~~~~~~~~~

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