Блог пользователя ikbal

Автор ikbal, 14 лет назад, По-английски

N<=10^4

//includes

using namespace std;

template inline T abs ( T a ){return a>0? a : -a;}

typedef pair<int,int> ii;

typedef long long Lint;

const int MAXN = 1e4+100;

const int inf = 1e9+5;

const Lint mod = 1e9+7;

int N;

int ar[MAXN];

Lint dn[2][MAXN];

void add(Lint &a,Lint b){ b%=mod; a = (a+b)%mod; if(a<0) a+=mod; }

int main(){

//~ freopen("f.in","r",stdin);
//~ freopen("f.out","w",stdout);

cin >> N ; 

For(i,1,N) scanf(" %d",ar+i);

if(ar[N]!=0 && ar[N]!=-1) return cout << 0 << endl, 0 ;
if(ar[N]==-1) ar[N]=0;

if(ar[1]!=0 && ar[1]!=-1) return cout << 0 << endl, 0 ;
if(ar[1]==-1) ar[1]=0;

dn[N&1][0] = 1LL;

for(int i=N-1;i>0;i--){

    memset(dn[i&1],0,sizeof dn[i&1]);

    if(ar[i]==-1){

        Rep(k,0,MAXN){
            if(k>0) add(dn[i&1][k],dn[(i+1)&1][k-1]);
            add(dn[i&1][k],dn[(i+1)&1][k]);
            if(k<MAXN) add(dn[i&1][k],dn[(i+1)&1][k+1]);
        }

    }else{

        int k = ar[i];

        if(k>0) add(dn[i&1][k],dn[(i+1)&1][k-1]);
        add(dn[i&1][k],dn[(i+1)&1][k]);
        if(k<MAXN) add(dn[i&1][k],dn[(i+1)&1][k+1]);

    }

}

cout << dn[1][0] << endl;

return 0;

}

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
14 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

First, one can notice that the maximal possible height is 5000. This observation will speed up your solution twice. Also it's better not to use long long when it isn't necessary. The last thing is to make your function add inline. And the main step: you don't need to use the % operation in this problem at all. Just subtract mod every time the number exceeds it. With these four optimizations my code works 0.3s on the maxtest.