oj.uz

Submission #907814

# Submission time Handle Problem Language Result Execution time Memory
907814 2024-01-16T05:00:11 Z ibm2006 Ljetopica (COI19_ljetopica) C++17
17 / 100
 59 ms 230292 KB 
#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

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.0

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

Subtask #2
0 / 14.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 230228 KB Output is correct
2 Correct 55 ms 230144 KB Output is correct
3 Correct 56 ms 230152 KB Output is correct
4 Correct 57 ms 230228 KB Output is correct
5 Correct 55 ms 230292 KB Output is correct
6 Correct 59 ms 230104 KB Output is correct
7 Correct 58 ms 230252 KB Output is correct
8 Correct 54 ms 230228 KB Output is correct
9 Correct 54 ms 230232 KB Output is correct
10 Correct 55 ms 230232 KB Output is correct

Subtask #4
0 / 61.0

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