Timus-2018. The Debut Album

T
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; }
Code language: PHP (php)

About the author

Sheikh Arman Hossain
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!