CSES - Leirikisa 5 - Results
Submission details
Task:baka
Sender:siirikuoppala
Submission time:2016-08-02 17:07:31 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#10.14 sdetails
#20.12 sdetails
#30.15 sdetails
#40.15 sdetails
#50.13 sdetails
#60.14 sdetails
#70.16 sdetails
#80.14 sdetails
#90.14 sdetails
#100.14 sdetails
#110.13 sdetails
#120.14 sdetails

Code

#include <iostream>
using namespace std;
typedef long long ll;
#define M 1000000007
ll t[10101][10101];
int A[10101];
int main(){
    int n;
    cin >> n;
    for(int i=0; i<n; ++i){
        cin >> A[i];
    }
    A[0]=0; A[n-1]=0;
    t[0][0]=1;
    for(int i=1; i<n; ++i){
        int h=A[i-1]+1;
        if(A[i]!=-1){
            int u=A[i];
            t[i][u]= t[i-1][u]+t[i-1][u+1];
            if(u>0) t[i][u]+=t[i-1][u-1];
            t[i][u]%=M;
            continue;
        }
        for(int j=0; j<=h; ++j){
            if(j>0) t[i][j]+= t[i-1][j-1];
            t[i][j]+=t[i-1][j];
            t[i][j]+=t[i-1][j+1];
            t[i][j]%=M;
        }
        A[i]=h;
    }
    cout << t[n-1][0];
}

Test details

Test 1

Verdict:

input
WA

correct output
13

user output
(empty)

Test 2

Verdict:

input
UNUCIC

correct output
36

user output
(empty)

Test 3

Verdict:

input
MACDNKIHFGBEHOJ

correct output
74

user output
(empty)

Test 4

Verdict:

input
ABCDEFGHIJKLMNO

correct output
75

user output
(empty)

Test 5

Verdict:

input
NCC

correct output
13

user output
(empty)

Test 6

Verdict:

input
AUUI

correct output
26

user output
(empty)

Test 7

Verdict:

input
UOEAIAOIUE

correct output
56

user output
(empty)

Test 8

Verdict:

input
AOEUIIUEAOEAOIO

correct output
82

user output
(empty)

Test 9

Verdict:

input
CFILOSVZXQCPFZO

correct output
102

user output
(empty)

Test 10

Verdict:

input
BEHKNRUYKRUBNE

correct output
89

user output
(empty)

Test 11

Verdict:

input
ADGJMPTWTPMJGDA

correct output
94

user output
(empty)

Test 12

Verdict:

input
UNUCICA

correct output
39

user output
(empty)