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

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

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
  • Проголосовать: не нравится

»
11 лет назад, # |
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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    thanks

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      In the first edit of my previous comment I forgot the main thing: never use the % operation in such problems!

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Actually, I use long longs and modulos like a lunatic, and still get 0.4 seconds on the largest test case :D EDIT: after an optimization (not affecting modulos or long longs), it's 0.2s. Here.

    Even the optimalization of max. height 5000 is sufficient to get rid of TLEs (around 0.7s on the largest test case). The remaining optimizations are quite insignificant in comparison.