Submission #836646


Source Code Expand

Copy
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) do { \
    fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
    _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif

template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }

void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
    _R(head);
    R(tail...);
}

template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
    for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
        if ( i!=x.cbegin() ) putchar(' ');
        _W(*i);
    }
}

void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
    _W(head);
    putchar(sizeof...(tail)?' ':'\n');
    W(tail...);
}

#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
    freopen(name ".in","r",stdin); \
    freopen(name ".out","w",stdout); \
} while (0)
#endif

// }}}

const int N=5010;
const LL MOD=1e9+7;
int n,m;
char s[N];
LL dp[2][N][N];
int main() {
    R(n,s);
    m=strlen(s);
    dp[0][0][0]=1;
    int u=0;
    REP(i,n) {
        REP(j,n+1) REP(k,n+1) dp[u^1][j][k]=0;
        REP(j,n+1) REP(k,n+1) {
            int me=dp[u][j][k]%MOD;
            if ( me==0 ) continue;
            if ( k==0 && j<n ) dp[u^1][j+1][k]+=me;
            dp[u^1][j][k+1]+=me+me;
            if ( k>0 ) dp[u^1][j][k-1]+=me;
            if ( j==0 && k==0 ) dp[u^1][0][0]+=me;
        }
        u^=1;
    }
    int ans=dp[u][m][0]%MOD;
    W(ans);
    return 0;
}

Submission Info

Submission Time
Task F - Unhappy Hacking
User shik
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3451 Byte
Status TLE
Exec Time 2141 ms
Memory 391680 KB

Compile Error

./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:46: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                              ^
./Main.cpp: In function ‘void _R(int&)’:
./Main.cpp:61:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( int &x ) { scanf("%d",&x); }
                                   ^
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                               ^
./Main.cpp: In function ‘void _R(double&)’:
./Main.cpp:63:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-resu...

Judge Result

Set Name Sample Sub1 Sub2
Score / Max Score 0 / 0 400 / 400 0 / 400
Status
AC × 2
TLE × 1
AC × 23
AC × 24
TLE × 20
Set Name Test Cases
Sample 0_01, 0_02, 0_03
Sub1 0_01, 0_02, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24
Sub2 0_01, 0_02, 0_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24, 2_25, 2_26, 2_27, 2_28, 2_29, 2_30, 2_31, 2_32, 2_33, 2_34, 2_35, 2_36, 2_37, 2_38, 2_39, 2_40, 2_41, 2_42, 2_43, 2_44
Case Name Status Exec Time Memory
0_01 AC 4 ms 256 KB
0_02 AC 165 ms 4096 KB
0_03 TLE 2141 ms 391680 KB
1_04 AC 4 ms 256 KB
1_05 AC 165 ms 4096 KB
1_06 AC 165 ms 4096 KB
1_07 AC 165 ms 4096 KB
1_08 AC 165 ms 4096 KB
1_09 AC 165 ms 4096 KB
1_10 AC 165 ms 4096 KB
1_11 AC 165 ms 4096 KB
1_12 AC 165 ms 4096 KB
1_13 AC 165 ms 4096 KB
1_14 AC 165 ms 4096 KB
1_15 AC 162 ms 3968 KB
1_16 AC 162 ms 3968 KB
1_17 AC 158 ms 3968 KB
1_18 AC 158 ms 3968 KB
1_19 AC 156 ms 3968 KB
1_20 AC 7 ms 768 KB
1_21 AC 55 ms 2432 KB
1_22 AC 8 ms 896 KB
1_23 AC 137 ms 3712 KB
1_24 AC 88 ms 3072 KB
2_25 TLE 2140 ms 391680 KB
2_26 TLE 2141 ms 391680 KB
2_27 TLE 2141 ms 391680 KB
2_28 TLE 2141 ms 391680 KB
2_29 TLE 2141 ms 391680 KB
2_30 TLE 2137 ms 391680 KB
2_31 TLE 2141 ms 391680 KB
2_32 TLE 2141 ms 391680 KB
2_33 TLE 2140 ms 391680 KB
2_34 TLE 2141 ms 391680 KB
2_35 TLE 2141 ms 391552 KB
2_36 TLE 2137 ms 391168 KB
2_37 TLE 2140 ms 391296 KB
2_38 TLE 2141 ms 391296 KB
2_39 TLE 2140 ms 391296 KB
2_40 TLE 2136 ms 344704 KB
2_41 TLE 2122 ms 183552 KB
2_42 TLE 2140 ms 381312 KB
2_43 TLE 2126 ms 229760 KB
2_44 AC 1423 ms 11520 KB