Submission #1792487


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
ll dp[256][256][256];
ll sum[256][256],sum2[256][256];
int n,a[256];
int main(){
	cin>>n;
	rep(i,n){
		cin>>a[i];
		sum2[i][i]++;
	}
	if(a[0] != 1){
		puts("0"); return 0;
	}
	for(int i=0;i<n-1;i++){
		dp[i][i+1][i+1] = 1;
		sum2[i][i+1] ++;
		if(i+2 == n || a[i+1] < a[i+2]) sum[i][i+1]++;
	}
	for(int len=3;len<=n;len++){
		for(int i=0;i<n;i++){
			if(i+len-1 >= n) break;
			for(int j=i+1;j<=i+len-1;j++){
				
				dp[i][i+len-1][j] = sum[i][j-1] * sum2[j][i+len-1] % mod;
				if(j==i+1) dp[i][i+len-1][j] += sum2[j][i+len-1];
				dp[i][i+len-1][j] %= mod;
				if(i+len == n || a[j] < a[i+len]){
					sum[i][i+len-1] = (sum[i][i+len-1]+dp[i][i+len-1][j])%mod;
				}
				sum2[i][i+len-1] = (sum2[i][i+len-1]+dp[i][i+len-1][j])%mod;
			}
		}
	}
//	cout<<sum2[1][2]<<endl;
	//cout<<dp[0][n-1][1]<<dp[0][n-1][2]<<dp[0][n-1][3]<<endl;
	cout<<sum[0][n-1]<<endl;
}

Submission Info

Submission Time
Task G - スタンプラリー
User IH19980412
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1514 Byte
Status AC
Exec Time 112 ms
Memory 131328 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 27
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 2 ms 4352 KB
01-03.txt AC 8 ms 25216 KB
01-04.txt AC 108 ms 131328 KB
01-05.txt AC 109 ms 131328 KB
01-06.txt AC 109 ms 131328 KB
01-07.txt AC 108 ms 131328 KB
01-08.txt AC 2 ms 768 KB
01-09.txt AC 1 ms 256 KB
01-10.txt AC 111 ms 131328 KB
01-11.txt AC 65 ms 104192 KB
01-12.txt AC 112 ms 131328 KB
01-13.txt AC 75 ms 110464 KB
01-14.txt AC 109 ms 131328 KB
01-15.txt AC 81 ms 114688 KB
01-16.txt AC 106 ms 131328 KB
01-17.txt AC 103 ms 131328 KB
01-18.txt AC 111 ms 131328 KB
01-19.txt AC 109 ms 131328 KB
01-20.txt AC 103 ms 131328 KB
01-21.txt AC 86 ms 120960 KB
sample-01.txt AC 2 ms 2304 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 5 ms 14848 KB