結果

問題 No.790 ちきんの括弧並べ
ユーザー lightning
提出日時 2019-03-21 18:06:04
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 1,595 bytes
コンパイル時間 1,601 ms
コンパイル使用メモリ 172,116 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-19 01:47:36
合計ジャッジ時間 2,345 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#define Rep(i,n) for(int i=0;i<n;i++)
#define For(i,n1,n2) for(int i=n1;i<n2;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
#define all(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define TDARRAY(int,a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) {if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a, T b) {if(a>b){a=b;return 1;}return 0;}

int n;

vector<int> demical(ll n,int k,int l){
    vector<int> rtn(l);
    REP(i,l){
        rtn[i]=n%k;
        n/=k;
    }
    //while(n>0){
    //rtn.push_back(n%k);
    //n/=k;
    //}
    return rtn;
}

int main(){
    cin >> n;
    vector<int> b(n,0);
    vector<int> c(n,0);
    b[0]=1;
    c[0]=0;
    vector<vector<int>> bit(pow(2,n));
    REP(i,pow(2,n)){
        bit[i]=demical(i,2,n);
    }
    FOR(i,1,n){
        b[i] = b[i-1]+c[i-1];
        FOR(j,1,pow(2,i)){
            vector<int> s;
            int con = 1;
            
            REP(k,i){
                if(bit[j][k]==0){
                    con++;
                }else{
                    s.push_back(con);
                    con=1;
                }
            }
            s.push_back(con);
            con=1;
        
            int sb=1;
            REP(k,s.size()){
                sb*=b[s[k]-1];
            }
            c[i]+=sb;
        }
        
        
    }
    put(b[n-1]+c[n-1]);
    return 0;
}
0