Timus-2018. The Debut Album

Problem NameThe Debut Album
JudgeTimus
Problem Linkhttps://acm.timus.ru/problem.aspx?space=1&num=2018
Algorithms & DSDynamic Programming
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define PB push_back
#define VST(V) sort(V.begin(),V.end())
#define VSTrev(V) sort(V.begin(),V.end(),greater<long long int>())
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll mod=1e9+7;
ll dp[3][4][310];
int main()
{
    // freopen("1input.txt","r",stdin);
    fast;
    ll tcase=1;
    //cin>>tcase;
    for(ll test=1; test<=tcase; test++)
    {
        ll n,a,b;
        cin>>n>>a>>b;
        for(ll k=1; k<3; k++)
        {
            for(ll j=0; j<=(ll)max(a,b); j++)
            {
                dp[0][k][j]=0;
            }
        }
        dp[0][1][1]=1;
        dp[0][2][1]=1;
        ll curr=0;
        for(ll i=1; i<n; i++)
        {
            ll pre=curr;
            curr=1-curr;
            for(ll k=0; k<=(ll)max(a,b); k++)
            {
                dp[curr][1][k]=0;
                dp[curr][2][k]=0;
            }
            for(ll k=2; k<=a; k++)
            {
                dp[curr][1][k]+=dp[pre][1][k-1];
                dp[curr][1][k]%=mod;
            }
            for(ll k=1; k<=b; k++)
            {
                dp[curr][1][1]+=dp[pre][2][k];
                dp[curr][1][1]%=mod;
            }
            for(ll k=2; k<=b; k++)
            {
                dp[curr][2][k]+=dp[pre][2][k-1];
                dp[curr][2][k]%=mod;
            }
            for(ll k=1; k<=a; k++)
            {
                dp[curr][2][1]+=dp[pre][1][k];
                dp[curr][2][1]%=mod;
            }
        }
        ll ans=0;
        for(ll i=1; i<=a; i++)
        {
            ans+=dp[curr][1][i];
            ans%=mod;
        }
        for(ll i=1; i<=b; i++)
        {
            ans+=dp[curr][2][i];
            ans%=mod;
        }
        cout<<ans<<"\n";
    }
    return 0;
}
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
error: Alert: Content is protected !!