# CFR 750 D. New Year and Fireworks ( DP )

Problem - D - Codeforces

1 ≤ N ≤ 30
1 ≤ T[ i ] ≤ 5

O( 30 * 8 * 300 ^ 2 lg ( 30 * 8 * 300 ^ 2 ) ) / O( 30 * 8 * 300 ^ 2 )

```int N;
vi T;

void init(){
cin >> N;
T = vi( N );
for( int i = 0; i < N; ++i ){
cin >> T[ i ];
}
}

const int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
const int dy[] = { 1, 1, 0, -1, -1, -1, 0, 1 };

set< tuple< int, int, int, int > > vis;
set< pii > coordinate;

void preprocess(){
queue< tuple< int, int, int, int > > que;
que.emplace( 0, 0, 0, 0 );
vis.emplace( 0, 0, 0, 0 );
coordinate.emplace( 0, 0 );
while( not que.empty() ){
int step, x, y, dir; tie( step, x, y, dir ) = que.front(); que.pop();
int nx = x, ny = y;
for( int i = 0; i < T[ step ] - 1; ++i ){
nx += dx[ dir ];
ny += dy[ dir ];
coordinate.emplace( nx, ny );
}
if( step + 1 < N and not vis.count( make_tuple( step + 1, nx + dx[ ( dir + 1 ) % 8 ], ny + dy[ ( dir + 1 ) % 8 ], ( dir + 1 ) % 8 ) ) ){
vis.emplace( step + 1, nx + dx[ ( dir + 1 ) % 8 ], ny + dy[ ( dir + 1 ) % 8 ], ( dir + 1 ) % 8 );
coordinate.emplace( nx + dx[ ( dir + 1 ) % 8 ], ny + dy[ ( dir + 1 ) % 8 ] );
que.emplace( step + 1, nx + dx[ ( dir + 1 ) % 8 ], ny + dy[ ( dir + 1 ) % 8 ], ( dir + 1 ) % 8 );
}
if( step + 1 < N and not vis.count( make_tuple( step + 1, nx + dx[ ( dir - 1 + 8 ) % 8 ], ny + dy[ ( dir - 1 + 8 ) % 8 ], ( dir - 1 + 8 ) % 8 ) ) ){
vis.emplace( step + 1, nx + dx[ ( dir - 1 + 8 ) % 8 ], ny + dy[ ( dir - 1 + 8 ) % 8 ], ( dir - 1 + 8 ) % 8 );
coordinate.emplace( nx + dx[ ( dir - 1 + 8 ) % 8 ], ny + dy[ ( dir - 1 + 8 ) % 8 ] );
que.emplace( step + 1, nx + dx[ ( dir - 1 + 8 ) % 8 ], ny + dy[ ( dir - 1 + 8 ) % 8 ], ( dir - 1 + 8 ) % 8 );
}
}
}

void solve(){
cout << coordinate.size() << endl;
}
```