Submission #1204430
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define int long long typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define all(v) (v).begin(),(v).end() #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define pb push_back #define fi first #define se second template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} const int mod=1000000007; inline void add(int &a,int b){ a+=b; if(a>=mod)a-=mod; } int N; int C[333]; int dp[333][333]; int f[333][333]; signed main(){ cin>>N; rep(i,N)cin>>C[i]; if(C[0]!=1){ cout<<0<<endl; return 0; } for(int i=N-1;i>=0;i--){ memset(f,0,sizeof(f)); f[i+1][0]=1; for(int j=i+1;j<=N;j++){ for(int k=0;k<N;k++)add(f[j][k+1],f[j][k]); for(int k=j+1;k<=N;k++)add(f[k][C[j]],f[j][C[j]]*dp[j][k]%mod); } for(int j=i+1;j<=N;j++)dp[i][j]=f[j][N]; } cout<<dp[0][N]<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | G - スタンプラリー |
User | latte0119 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1223 Byte |
Status | AC |
Exec Time | 49 ms |
Memory | 1792 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
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 | 2 ms | 1152 KB |
01-02.txt | AC | 2 ms | 1152 KB |
01-03.txt | AC | 4 ms | 1280 KB |
01-04.txt | AC | 47 ms | 1792 KB |
01-05.txt | AC | 47 ms | 1792 KB |
01-06.txt | AC | 47 ms | 1792 KB |
01-07.txt | AC | 46 ms | 1792 KB |
01-08.txt | AC | 1 ms | 256 KB |
01-09.txt | AC | 1 ms | 256 KB |
01-10.txt | AC | 48 ms | 1792 KB |
01-11.txt | AC | 27 ms | 1664 KB |
01-12.txt | AC | 48 ms | 1792 KB |
01-13.txt | AC | 31 ms | 1664 KB |
01-14.txt | AC | 49 ms | 1792 KB |
01-15.txt | AC | 35 ms | 1664 KB |
01-16.txt | AC | 40 ms | 1792 KB |
01-17.txt | AC | 39 ms | 1792 KB |
01-18.txt | AC | 47 ms | 1792 KB |
01-19.txt | AC | 46 ms | 1792 KB |
01-20.txt | AC | 40 ms | 1792 KB |
01-21.txt | AC | 32 ms | 1664 KB |
sample-01.txt | AC | 2 ms | 1152 KB |
sample-02.txt | AC | 1 ms | 256 KB |
sample-03.txt | AC | 3 ms | 1152 KB |