Submission #907814

#	Time	Username	Problem	Language	Result	Execution time	Memory
907814		ibm2006	Ljetopica (COI19_ljetopica)	C++17	17 / 100	59 ms	230292 KiB

ljetopica

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,a[1100000],b[1100000],com[5500][5500],tw[5500],dp[1100][1100],ans;
char c;
const ll mod=1000000007;
ll C(ll x,ll y)
{
    if(x<0||y<0||y>x)
        return 0;
        return com[x][y];
}
ll two(ll x)
{
    return tw[x];
}
int main()
{
    tw[0]=1;
    com[0][0]=1;
    for(i=1;i<=5000;i++)
    {
        for(j=0;j<=i;j++)
        {
            if(j==0)
            {
                com[i][j]=1;
                continue;
            }
            com[i][j]=(com[i-1][j]+com[i-1][j-1])%mod;
        }
    }
    for(i=1;i<=5000;i++)
    {
        tw[i]=tw[i-1]*2%mod;
    }
    scanf("%lld %lld\n",&n,&k);
    for(i=1;i<n;i++)
    {
        scanf("%c",&c);
        if(c=='L')
        {
            a[i]=0;
        }
        else
        {
            a[i]=1;
        }
    }
    dp[1][0]=1;
    for(i=2;i<=n;i++)
    {
        for(j=0;j<i;j++)
        {
            if(a[n-i+1]==0)
            {
                if(j==0)
                {
                    dp[i][j]=dp[i-1][j]+C(i-2,j)*two(i-2)%mod;
                }
                else
                {dp[i][j]=dp[i-1][j]+C(i-2,j)*two(i-2)%mod+(two(i-2)*3+two(i-1)-1)*C(i-2,j-1)%mod-dp[i-1][j-1];}
                dp[i][j]%=mod;
                dp[i][j]=(dp[i][j]+mod)%mod;
            }
            else
            {
                if(j==0)
                {
                    dp[i][j]=dp[i-1][j]+C(i-2,j)*two(i-1)%mod;
                }
                else
                dp[i][j]=dp[i-1][j]+C(i-2,j)*two(i-1)%mod+(two(i)-1)*C(i-2,j-1)%mod-dp[i-1][j-1];
                dp[i][j]%=mod;
                dp[i][j]=(dp[i][j]+mod)%mod;
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        scanf("%01lld",&b[i]);
    }
    for(i=1;i<=n;i++)
    {
        scanf("%01lld",&b[i]);
    }

    if(k>=1)
    {
        ans=dp[n][k]+dp[n][k-1]+(two(n)-1+two(n-1))*C(n-1,k)%mod-dp[n][k]-dp[n][k-1];
    }
    else
    {
        ans=dp[n][k]+two(n)-1+two(n-1)-dp[n][k];
    }
    printf("%lld",ans%mod);
}

Compilation message (stderr)

ljetopica.cpp: In function 'll C(ll, ll)':
ljetopica.cpp:9:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    9 |     if(x<0||y<0||y>x)
      |     ^~
ljetopica.cpp:11:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   11 |         return com[x][y];
      |         ^~~~~~
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%lld %lld\n",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
ljetopica.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%c",&c);
      |         ~~~~~^~~~~~~~~
ljetopica.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%01lld",&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
ljetopica.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%01lld",&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

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