Submission #40528

#	Time	Username	Problem	Language	Result	Execution time	Memory
40528		jubairaraf	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	392 ms	284228 KiB

kangaroo

//#include <bits/stdc++.h>
#include <sstream>
#include<limits.h>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <complex>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>
#include <bitset>
#include <list>
#include <string.h>
#include <assert.h>
#include <time.h>
#include <fstream>
#include <numeric>
#include <cstring>

using namespace std;
template<class T1> void deb(T1 e1)
{
    cout<<e1<<endl;
}
template<class T1,class T2> void deb(T1 e1,T2 e2)
{
    cout<<e1<<" "<<e2<<endl;
}
template<class T1,class T2,class T3> void deb(T1 e1,T2 e2,T3 e3)
{
    cout<<e1<<" "<<e2<<" "<<e3<<endl;
}
template<class T1,class T2,class T3,class T4> void deb(T1 e1,T2 e2,T3 e3,T4 e4)
{
    cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<endl;
}
template<class T1,class T2,class T3,class T4,class T5> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5)
{
    cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<endl;
}
template<class T1,class T2,class T3,class T4,class T5,class T6> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5,T6 e6)
{
    cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<" "<<e6<<endl;
}


#define    pb   push_back
#define    pp   pop_back
#define    pi   2*acos(0.0)
#define    pf   printf
#define    sf   scanf
#define    EPS  1e-10
#define    clr(a)       memset(a,0,sizeof(a))
#define    full(a)      memset(a,63,sizeof(a))
#define    max3(a,b,c)  max(a,max(b,c))
#define    min3(a,b,c)  min(a,min(b,c))
#define    sf1(a)       scanf("%d",&a)
#define    sf2(a,b)     scanf("%d%d",&a,&b)
#define    sf3(a,b,c)   scanf("%d%d%d",&a,&b,&c)
#define    sf1ll(a)      scanf("%lld",&a)
#define    sf2ll(a,b)    scanf("%lld%lld",&a,&b)
#define    sf3ll(a,b,c)  scanf("%lld%lld%lld",&a,&b,&c)
#define    sf1d(a)      scanf("%lf",&a)
#define    sf2d(a,b)    scanf("%lf%lf",&a,&b)
#define    sf3d(a,b,c)  scanf("%lf%lf%lf",&a,&b,&c)
#define    READ(in)     freopen("in.txt","r",stdin);
#define    WRITE(out)   freopen("out.txt","w",stdout);
#define    _boost       ios_base::sync_with_stdio(0); cin.tie(0);
#define    sr_pr(s1)    printf("%s",s1.c_str())
#define    fo(i,n)      for(i=0;i<n;i++)
#define    mp           make_pair
#define    MAX
#define    MOD

typedef long long ll;
typedef unsigned long long ull;
//bitmask
/*int Set( int n, int pos ){
    return n = n|( 1<<pos );
}
bool check( int n, int pos ){
    return (bool)( n&( 1LL<<pos ) );
}
int reset( int n, int pos ){
    return n = n&~( 1<<pos );
}*/
/*BIGMOD
ll big_mod(ll a,ll b,ll m)
{
    long long int i,j,k,l; if(b==0) return 1;
    if(b%2==0){ k=big_mod(a,b/2,m); return ((k%m)*(k%m))%m;}
    else return((a%m)*(big_mod(a,b-1,m))%m)%m;
}
/*GCD
int gcd(int a,int b){ if(b==0) return a; return  gcd(b,a%b);}

/*PARENT_FIND
int pfind(int r)   return par[r]==r ? r : par[r]=pfind(par[r]);
}*/
/*BASE_CONVERT
int convert_base_big_TO_small(int num,int base,int ar1[])
{
    if(num==0) {ar1[0]=0;return 1;}
    int ar2[110],l=0;
    while(1)  { if(num<base) break;  ar2[l++]=num%base;  num/=base; }
    if(num>0) ar2[l++]=num;
    for(int i=0;i<l;i++) { ar1[i]=ar2[l-i-1];  }  return l;
}
int convert_base_small_TO_big(int ar1[],int base,int len)
{
    int pw[110],i,j,k; pw[0]=1;
    for(i=1;i<=len+1;i++) { pw[i]=pw[i-1]*2;//for 2 base to 10 base }
    int sum=0,l=0;
    for(i=len-1;i>=0;i--) { sum+=(ar1[l++]*pw[i]);//deb(sum); }
    return sum;
}
*/

int dx[]= {0,0,1,-1};
int dy[]= {-1,1,0,0};
//int dx[]= {1,-1,0,0,-1,-1,1,1};/*8 move*/
//int dy[]= {0,0,1,-1,1,-1,1,-1};/*8 move*/
//int dx[]={1,1,2,2,-1,-1,-2,-2};/*knight move*/
//int dy[]={2,-2,1,-1,2,-2,1,-1};/*knight move*/
#define MXK         450000
#define mx 400000
#define fs          first
#define sc          second
#define ll long long
#define mod  1000000007
typedef pair< long long, long long>pii;

ll dp[2005][2005][3][3];
int n,s,e;
ll dp_func(int pos,int com,int st,int en)
{
    if(com<0)return 0;
    if(pos==n){
        if(pos==s){
             return com==0;
        }
        if(pos==e){
            return com==0;
        }
        //cout<<com<<endl;
        return com==0;
    }
    if(dp[pos][com][st][en]!=-1)return dp[pos][com][st][en];
    ll& ret=dp[pos][com][st][en];
    ret=0;
    if(pos==s){
        if(com)ret+=dp_func(pos+1,com-1,1,en)*com;
        ret+=dp_func(pos+1,com,1,en);
        ret%=mod;
        return ret;
    }
    if(pos==e){
        if(com)ret+=dp_func(pos+1,com-1,st,1)*com;
      //  if(com)cout<<ret<<" "<<pos<<" "<<com<<endl;
        ret+=dp_func(pos+1,com,st,1);
        ret%=mod;
        return ret;
    }
    ret+=dp_func(pos+1,com-1,st,en)*(com*(com-1));
    ret+=dp_func(pos+1,com+1,st,en);
    if(st&&com)ret+=dp_func(pos+1,com-1,st,en)*com;
    if(en&&com)ret+=dp_func(pos+1,com-1,st,en)*com;
    ret%=mod;
    return ret;
}
int main()
{
    //READ(kangaroo);
  //  WRITE(kangaroo);
   int i,j,k,l,m;
   scanf("%d%d%d",&n,&s,&e);
   memset(dp,-1,sizeof dp);
   ll ans=dp_func(1,0,0,0);
   cout<<ans<<endl;


}

Compilation message (stderr)

kangaroo.cpp:103:1: warning: "/*" within comment [-Wcomment]
 /*GCD
 ^
kangaroo.cpp:106:1: warning: "/*" within comment [-Wcomment]
 /*PARENT_FIND
 ^
kangaroo.cpp: In function 'int main()':
kangaroo.cpp:184:8: warning: unused variable 'i' [-Wunused-variable]
    int i,j,k,l,m;
        ^
kangaroo.cpp:184:10: warning: unused variable 'j' [-Wunused-variable]
    int i,j,k,l,m;
          ^
kangaroo.cpp:184:12: warning: unused variable 'k' [-Wunused-variable]
    int i,j,k,l,m;
            ^
kangaroo.cpp:184:14: warning: unused variable 'l' [-Wunused-variable]
    int i,j,k,l,m;
              ^
kangaroo.cpp:184:16: warning: unused variable 'm' [-Wunused-variable]
    int i,j,k,l,m;
                ^
kangaroo.cpp:185:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d",&n,&s,&e);
                            ^

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49