Submission #29412

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back
#define P pair<int,int>
#define vp vector<P>
#define PP pair<P,int>
#define vpp vector<PP>
#define fi first
#define se second
#define INF (1<<30)
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define all(x) (x).begin(),(x).end()
int main(){
    int n,m;
    cin>>n>>m;
    vi vec(n);
    REP(i,n){
        cin>>vec[i];
    }
    set<int> se;
    REP(i,1<<n){
        int b=0;
        REP(j,n){
            if(i&(1<<j)){
                b+=vec[j];
            }
        }
        se.insert(b);
    }
    vi dp(m+1,INF);
    dp[0]=0;
    REP(i,m+1){
        for(auto j:se){
            if(i-j>=0){
                dp[i]=min(dp[i],dp[i-j]+1);
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

ステータス

項目	データ
問題	0088 - レジが壊れた
ユーザー名	SugarDragon5
投稿日時	2017-12-06 21:13:35
言語	C++17
状態	Accepted
得点	5
ソースコード長	987 Byte
最大実行時間	435 ms
最大メモリ使用量	1372 KB

セット

	セット	得点	Cases
1	ALL	5 / 5	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in-1	AC	23 ms	480 KB	1
in-2	AC	15 ms	636 KB	1
in-3	AC	18 ms	640 KB	1
in-4	AC	25 ms	1084 KB	1
in-5	AC	19 ms	1144 KB	1
in-6	AC	44 ms	1160 KB	1
in-7	AC	235 ms	1220 KB	1
in-8	AC	435 ms	1160 KB	1
in-9	AC	34 ms	1372 KB	1
in-10	AC	26 ms	836 KB	1
in-11	AC	21 ms	796 KB	1
in-12	AC	15 ms	892 KB	1
in-13	AC	37 ms	992 KB	1
in-14	AC	53 ms	700 KB	1
in-15	AC	19 ms	600 KB	1
in-16	AC	17 ms	540 KB	1
in-17	AC	15 ms	504 KB	1
in-18	AC	19 ms	576 KB	1
in-19	AC	15 ms	676 KB	1
in-20	AC	14 ms	476 KB	1
in-21	AC	16 ms	576 KB	1
in-22	AC	27 ms	640 KB	1
in-23	AC	26 ms	572 KB	1
in-24	AC	20 ms	668 KB	1
in-25	AC	17 ms	732 KB	1
in-26	AC	16 ms	556 KB	1
in-27	AC	14 ms	652 KB	1
in-28	AC	22 ms	724 KB	1
in-29	AC	18 ms	552 KB	1
in-30	AC	16 ms	572 KB	1
in-31	AC	17 ms	660 KB	1
in-32	AC	17 ms	724 KB	1
in-33	AC	19 ms	680 KB	1
in-34	AC	21 ms	628 KB	1
in-35	AC	31 ms	588 KB	1
in-36	AC	14 ms	644 KB	1
in-37	AC	18 ms	600 KB	1
in-38	AC	14 ms	792 KB	1
in-39	AC	24 ms	740 KB	1
in-40	AC	16 ms	672 KB	1
in-41	AC	23 ms	752 KB	1
in-42	AC	19 ms	692 KB	1
in-43	AC	37 ms	792 KB	1
in-44	AC	17 ms	832 KB	1
in-45	AC	17 ms	780 KB	1
in-46	AC	20 ms	732 KB	1
in-47	AC	22 ms	812 KB	1
in-48	AC	16 ms	740 KB	1
in-49	AC	23 ms	696 KB	1
in-50	AC	21 ms	728 KB	1
in-51	AC	13 ms	700 KB	1
in-52	AC	14 ms	796 KB	1
in-53	AC	16 ms	732 KB	1
in-54	AC	20 ms	808 KB	1
in-55	AC	18 ms	872 KB	1
in-56	AC	21 ms	824 KB	1
in-57	AC	13 ms	628 KB	1
in-58	AC	17 ms	732 KB	1
in-59	AC	15 ms	832 KB	1
in-60	AC	23 ms	740 KB	1
in-61	AC	14 ms	828 KB	1
in-62	AC	17 ms	772 KB	1
in-63	AC	19 ms	744 KB	1
in-64	AC	19 ms	960 KB	1
in-65	AC	19 ms	856 KB	1
in-66	AC	16 ms	696 KB	1
in-67	AC	25 ms	900 KB	1
in-68	AC	28 ms	760 KB	1
in-69	AC	18 ms	884 KB	1
in-70	AC	61 ms	1036 KB	1
in-71	AC	24 ms	1084 KB	1
in-72	AC	22 ms	660 KB	1
in-73	AC	19 ms	764 KB	1
in-74	AC	14 ms	976 KB	1
in-75	AC	354 ms	1140 KB	1
in-76	AC	22 ms	792 KB	1
in-77	AC	22 ms	1096 KB	1
in-78	AC	31 ms	1064 KB	1
in-79	AC	30 ms	960 KB	1
in-80	AC	38 ms	1080 KB	1
in-81	AC	390 ms	1108 KB	1
in-82	AC	17 ms	984 KB	1
in-83	AC	19 ms	872 KB	1