oj.uz

Submission #40528

# Submission time Handle Problem Language Result Execution time Memory
40528 2018-02-04T08:33:18 Z jubairaraf Kangaroo (CEOI16_kangaroo) C++14
100 / 100
 392 ms 284228 KB 
//#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

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

# Verdict Execution time Memory Grader output
1 Correct 209 ms 283668 KB Output is correct
2 Correct 204 ms 283668 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 283668 KB Output is correct
2 Correct 204 ms 283668 KB Output is correct
3 Correct 204 ms 283668 KB Output is correct
4 Correct 216 ms 283752 KB Output is correct
5 Correct 207 ms 283804 KB Output is correct
6 Correct 210 ms 283920 KB Output is correct
7 Correct 207 ms 283920 KB Output is correct
8 Correct 208 ms 283920 KB Output is correct
9 Correct 205 ms 283920 KB Output is correct
10 Correct 208 ms 283960 KB Output is correct
11 Correct 207 ms 283960 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 283668 KB Output is correct
2 Correct 204 ms 283668 KB Output is correct
3 Correct 204 ms 283668 KB Output is correct
4 Correct 216 ms 283752 KB Output is correct
5 Correct 207 ms 283804 KB Output is correct
6 Correct 210 ms 283920 KB Output is correct
7 Correct 207 ms 283920 KB Output is correct
8 Correct 208 ms 283920 KB Output is correct
9 Correct 205 ms 283920 KB Output is correct
10 Correct 208 ms 283960 KB Output is correct
11 Correct 207 ms 283960 KB Output is correct
12 Correct 209 ms 283976 KB Output is correct
13 Correct 208 ms 284064 KB Output is correct
14 Correct 210 ms 284064 KB Output is correct
15 Correct 212 ms 284064 KB Output is correct
16 Correct 207 ms 284092 KB Output is correct
17 Correct 209 ms 284092 KB Output is correct
18 Correct 213 ms 284092 KB Output is correct
19 Correct 213 ms 284092 KB Output is correct
20 Correct 209 ms 284092 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 283668 KB Output is correct
2 Correct 204 ms 283668 KB Output is correct
3 Correct 204 ms 283668 KB Output is correct
4 Correct 216 ms 283752 KB Output is correct
5 Correct 207 ms 283804 KB Output is correct
6 Correct 210 ms 283920 KB Output is correct
7 Correct 207 ms 283920 KB Output is correct
8 Correct 208 ms 283920 KB Output is correct
9 Correct 205 ms 283920 KB Output is correct
10 Correct 208 ms 283960 KB Output is correct
11 Correct 207 ms 283960 KB Output is correct
12 Correct 209 ms 283976 KB Output is correct
13 Correct 208 ms 284064 KB Output is correct
14 Correct 210 ms 284064 KB Output is correct
15 Correct 212 ms 284064 KB Output is correct
16 Correct 207 ms 284092 KB Output is correct
17 Correct 209 ms 284092 KB Output is correct
18 Correct 213 ms 284092 KB Output is correct
19 Correct 213 ms 284092 KB Output is correct
20 Correct 209 ms 284092 KB Output is correct
21 Correct 224 ms 284092 KB Output is correct
22 Correct 227 ms 284092 KB Output is correct
23 Correct 235 ms 284092 KB Output is correct
24 Correct 386 ms 284228 KB Output is correct
25 Correct 366 ms 284228 KB Output is correct
26 Correct 375 ms 284228 KB Output is correct
27 Correct 392 ms 284228 KB Output is correct
28 Correct 303 ms 284228 KB Output is correct