Submission #172209


Source Code Expand

Copy
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>

using namespace std; using namespace placeholders;

using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VS = vector<string>;
using SS = stringstream;
using PII = pair<int,int>;
using VPII = vector< pair<int,int> >;
template < typename T = int > using VT = vector<T>;
template < typename T = int > using VVT = VT< VT<T> >;
template < typename T = int > using LIM = numeric_limits<T>;

template < typename T > inline T fromString( const string &s ){ T res; istringstream iss( s ); iss >> res; return res; };
template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()
#define AALL( a, t ) (t*)a, (t*)a + sizeof( a ) / sizeof( t )
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

constexpr int MOD = 1000000007;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	if ( 2000 < *max_element( ALL( as ) ) )
	{
		return 1;
	}

	VVI dp( n + 1, VI( 2001 ) );
	dp[0][0] = 1;

	REP( i, 0, n )
	{
		REP( j, 0, 2001 )
		{
			REP( k, j, 2001 )
			{
				if ( as[i] != -1 && as[i] != k )
				{
					continue;
				}

				( dp[ i + 1 ][k] += dp[i][j] ) %= MOD;
			}
		}
	}

	cout << dp[n][ as.back() ] << endl;

	return 0;
}

Submission Info

Submission Time
Task C - タコヤ木
User torus711
Language C++11 (GCC 4.8.1)
Score 50
Code Size 2071 Byte
Status TLE
Exec Time 2037 ms
Memory 16672 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 50 / 50 0 / 30 0 / 20
Status
AC × 2
RE × 1
AC × 14
AC × 18
TLE × 8
AC × 16
TLE × 8
RE × 12
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 35 ms 800 KB
sample_02.txt AC 54 ms 796 KB
sample_03.txt RE 21 ms 928 KB
subtask1_01.txt AC 27 ms 924 KB
subtask1_02.txt AC 30 ms 800 KB
subtask1_03.txt AC 40 ms 800 KB
subtask1_04.txt AC 683 ms 1444 KB
subtask1_05.txt AC 618 ms 1572 KB
subtask1_06.txt AC 497 ms 1376 KB
subtask1_07.txt AC 837 ms 1568 KB
subtask1_08.txt AC 309 ms 1564 KB
subtask1_09.txt AC 738 ms 1700 KB
subtask1_10.txt AC 513 ms 1696 KB
subtask1_11.txt AC 508 ms 1560 KB
subtask1_12.txt AC 733 ms 1572 KB
subtask2_01.txt AC 27 ms 932 KB
subtask2_02.txt AC 35 ms 808 KB
subtask2_03.txt AC 46 ms 804 KB
subtask2_04.txt AC 1959 ms 5024 KB
subtask2_05.txt TLE 2032 ms 12448 KB
subtask2_06.txt TLE 2031 ms 5016 KB
subtask2_07.txt TLE 2032 ms 16548 KB
subtask2_08.txt TLE 2032 ms 16556 KB
subtask2_09.txt TLE 2032 ms 16560 KB
subtask2_10.txt TLE 2033 ms 16556 KB
subtask2_11.txt TLE 2037 ms 16628 KB
subtask2_12.txt TLE 2032 ms 16672 KB
subtask3_01.txt RE 21 ms 796 KB
subtask3_02.txt RE 21 ms 924 KB
subtask3_03.txt RE 24 ms 796 KB
subtask3_04.txt RE 22 ms 804 KB
subtask3_05.txt RE 21 ms 804 KB
subtask3_06.txt RE 22 ms 928 KB
subtask3_07.txt RE 22 ms 808 KB
subtask3_08.txt RE 22 ms 800 KB
subtask3_09.txt RE 26 ms 924 KB
subtask3_10.txt RE 21 ms 924 KB
subtask3_11.txt RE 22 ms 932 KB
subtask3_12.txt RE 23 ms 800 KB