Submission #641763
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;} template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;} const int mod=1000000007; const int L=3000; string S; int K; int N; vint G[3000]; bool isroot[3000]; int w[3000]; vint dp[3000]; int ord[3000]; vint tmp; void solve(int v,int p=-1){ w[v]=0; dp[v][L]=1; rep(hoge,G[v].size()){ int to=G[v][hoge]; if(to==p)continue; solve(to,v); if(w[v]<w[to]){ swap(ord[v],ord[to]); swap(w[v],w[to]); } fill(all(tmp),0); int ww=w[v]; vint &f=dp[ord[to]],&t=dp[ord[v]]; for(int i=L-w[to];i<=L+w[to];i++){ for(int j=L-w[v];j<=L+w[v];j++){ int foo=(i-L)+(j-L)+L; if(foo<0||foo>2*L)continue; tmp[foo]=(tmp[foo]+f[i]*t[j])%mod; chmax(ww,foo-L); } } chmax(w[v],ww); rep(i,L*2+1)t[i]=tmp[i]; //cout<<to<<"->"<<v<<":";for(int i=L-K;i<=L+K;i++)cout<<t[i]<<" ";cout<<endl; } fill(all(tmp),0); vint &t=dp[ord[v]]; rep(i,L*2+1){ if(i)tmp[i-1]+=t[i]; if(i<L*2)tmp[i+1]+=t[i]; tmp[i]+=t[i]*2; } rep(i,L*2+1){ if(L-K<=i&&i<=L+K)t[i]=tmp[i]; else t[i]=0; } w[v]=min(w[v]+1,L); //cout<<v<<":";for(int i=L-K;i<=L+K;i++)cout<<t[i]<<" ";cout<<endl; } signed main(){ cin>>S>>K;K/=2; stack<int>st; rep(i,S.size()){ if(S[i]==')'){ int tmp=st.top();st.pop(); if(st.empty())isroot[tmp]=true; else{ int foo=st.top(); G[foo].pb(tmp); G[tmp].pb(foo); } } else{ st.push(N++); } } rep(i,N)dp[i].resize(L*2+1); rep(i,N)ord[i]=i; tmp.resize(L*2+1); int ans=1; rep(i,N)if(isroot[i]){ solve(i); int sum=0; for(int j=L-K;j<=L+K;j++)sum+=dp[ord[i]][j]; ans=sum%mod*ans%mod; } cout<<ans<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 特別講演「括弧列と塗り分け」 |
User | latte0119 |
Language | C++ (GCC 4.9.2) |
Score | 70 |
Code Size | 2590 Byte |
Status | AC |
Exec Time | 285 ms |
Memory | 71764 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 10 / 10 | 10 / 10 | 50 / 50 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt |
Subtask1 | 00_example_02.txt, 00_example_03.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt |
Subtask2 | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 20_tree_01.txt, 20_tree_02.txt, 20_tree_03.txt, 20_tree_04.txt, 20_tree_05.txt, 20_tree_06.txt, 30_forest_01.txt, 30_forest_02.txt, 30_forest_03.txt, 30_forest_04.txt, 30_forest_05.txt, 30_forest_06.txt, 40_hand_01.txt, 40_hand_02.txt, 40_hand_03.txt, 40_hand_04.txt, 40_hand_05.txt, 40_hand_06.txt, 40_hand_07.txt, 40_hand_08.txt, 40_hand_09.txt, 45_zero_01.txt, 45_zero_02.txt, 45_zero_03.txt, 45_zero_04.txt, 45_zero_05.txt, 45_zero_06.txt, 45_zero_07.txt, 45_zero_08.txt, 45_zero_09.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 20_tree_01.txt, 20_tree_02.txt, 20_tree_03.txt, 20_tree_04.txt, 20_tree_05.txt, 20_tree_06.txt, 30_forest_01.txt, 30_forest_02.txt, 30_forest_03.txt, 30_forest_04.txt, 30_forest_05.txt, 30_forest_06.txt, 40_hand_01.txt, 40_hand_02.txt, 40_hand_03.txt, 40_hand_04.txt, 40_hand_05.txt, 40_hand_06.txt, 40_hand_07.txt, 40_hand_08.txt, 40_hand_09.txt, 45_zero_01.txt, 45_zero_02.txt, 45_zero_03.txt, 45_zero_04.txt, 45_zero_05.txt, 45_zero_06.txt, 45_zero_07.txt, 45_zero_08.txt, 45_zero_09.txt, 50_tree_01.txt, 50_tree_02.txt, 50_tree_03.txt, 50_tree_04.txt, 50_tree_05.txt, 50_tree_06.txt, 60_forest_01.txt, 60_forest_02.txt, 60_forest_03.txt, 60_forest_04.txt, 60_forest_05.txt, 60_forest_06.txt, 65_zero_01.txt, 65_zero_02.txt, 65_zero_03.txt, 65_zero_04.txt, 65_zero_05.txt, 65_zero_06.txt, 65_zero_07.txt, 65_zero_08.txt, 65_zero_09.txt, 70_hand_01.txt, 70_hand_02.txt, 70_hand_03.txt, 70_hand_04.txt, 70_hand_05.txt, 70_hand_06.txt, 70_hand_07.txt, 70_hand_08.txt, 70_hand_09.txt, 70_hand_10.txt, 70_hand_11.txt, 70_hand_12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 31 ms | 1184 KB |
00_example_02.txt | AC | 27 ms | 1116 KB |
00_example_03.txt | AC | 44 ms | 1260 KB |
00_example_04.txt | AC | 29 ms | 1948 KB |
10_small_01.txt | AC | 27 ms | 1116 KB |
10_small_02.txt | AC | 27 ms | 1176 KB |
10_small_03.txt | AC | 28 ms | 1248 KB |
10_small_04.txt | AC | 29 ms | 1244 KB |
10_small_05.txt | AC | 27 ms | 1248 KB |
10_small_06.txt | AC | 27 ms | 1308 KB |
10_small_07.txt | AC | 29 ms | 1244 KB |
10_small_08.txt | AC | 30 ms | 1248 KB |
10_small_09.txt | AC | 29 ms | 1308 KB |
20_tree_01.txt | AC | 33 ms | 2972 KB |
20_tree_02.txt | AC | 34 ms | 3036 KB |
20_tree_03.txt | AC | 34 ms | 3168 KB |
20_tree_04.txt | AC | 28 ms | 1648 KB |
20_tree_05.txt | AC | 30 ms | 1752 KB |
20_tree_06.txt | AC | 31 ms | 2008 KB |
30_forest_01.txt | AC | 35 ms | 2912 KB |
30_forest_02.txt | AC | 36 ms | 3036 KB |
30_forest_03.txt | AC | 36 ms | 3160 KB |
30_forest_04.txt | AC | 29 ms | 1628 KB |
30_forest_05.txt | AC | 30 ms | 1756 KB |
30_forest_06.txt | AC | 31 ms | 2012 KB |
40_hand_01.txt | AC | 38 ms | 3484 KB |
40_hand_02.txt | AC | 37 ms | 3488 KB |
40_hand_03.txt | AC | 36 ms | 3428 KB |
40_hand_04.txt | AC | 36 ms | 3420 KB |
40_hand_05.txt | AC | 36 ms | 3416 KB |
40_hand_06.txt | AC | 37 ms | 3416 KB |
40_hand_07.txt | AC | 38 ms | 3416 KB |
40_hand_08.txt | AC | 36 ms | 3416 KB |
40_hand_09.txt | AC | 37 ms | 3416 KB |
45_zero_01.txt | AC | 36 ms | 3420 KB |
45_zero_02.txt | AC | 37 ms | 3472 KB |
45_zero_03.txt | AC | 36 ms | 3420 KB |
45_zero_04.txt | AC | 36 ms | 3452 KB |
45_zero_05.txt | AC | 37 ms | 3412 KB |
45_zero_06.txt | AC | 38 ms | 3488 KB |
45_zero_07.txt | AC | 36 ms | 3416 KB |
45_zero_08.txt | AC | 35 ms | 3528 KB |
45_zero_09.txt | AC | 36 ms | 3420 KB |
50_tree_01.txt | AC | 79 ms | 17628 KB |
50_tree_02.txt | AC | 49 ms | 8020 KB |
50_tree_03.txt | AC | 108 ms | 25896 KB |
50_tree_04.txt | AC | 99 ms | 20960 KB |
50_tree_05.txt | AC | 174 ms | 44244 KB |
50_tree_06.txt | AC | 248 ms | 63956 KB |
60_forest_01.txt | AC | 85 ms | 17628 KB |
60_forest_02.txt | AC | 52 ms | 7896 KB |
60_forest_03.txt | AC | 113 ms | 25944 KB |
60_forest_04.txt | AC | 98 ms | 20952 KB |
60_forest_05.txt | AC | 181 ms | 44256 KB |
60_forest_06.txt | AC | 248 ms | 63832 KB |
65_zero_01.txt | AC | 138 ms | 34132 KB |
65_zero_02.txt | AC | 96 ms | 21980 KB |
65_zero_03.txt | AC | 217 ms | 56456 KB |
65_zero_04.txt | AC | 176 ms | 46808 KB |
65_zero_05.txt | AC | 228 ms | 63064 KB |
65_zero_06.txt | AC | 143 ms | 35796 KB |
65_zero_07.txt | AC | 107 ms | 24608 KB |
65_zero_08.txt | AC | 213 ms | 58452 KB |
65_zero_09.txt | AC | 193 ms | 57376 KB |
70_hand_01.txt | AC | 273 ms | 71556 KB |
70_hand_02.txt | AC | 273 ms | 71520 KB |
70_hand_03.txt | AC | 275 ms | 71448 KB |
70_hand_04.txt | AC | 265 ms | 71508 KB |
70_hand_05.txt | AC | 254 ms | 71440 KB |
70_hand_06.txt | AC | 262 ms | 71508 KB |
70_hand_07.txt | AC | 285 ms | 71520 KB |
70_hand_08.txt | AC | 261 ms | 71764 KB |
70_hand_09.txt | AC | 242 ms | 71392 KB |
70_hand_10.txt | AC | 285 ms | 71448 KB |
70_hand_11.txt | AC | 258 ms | 71584 KB |
70_hand_12.txt | AC | 234 ms | 71508 KB |