#if !defined(__clang__) && defined(__GNUC__) && !defined(LOCAL) #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #if !defined(LOCAL) #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #elif 1 #include #else import std; #endif namespace inner { // clang-format off #define c_ constexpr #define t_ template std::vector isprime_seq(size_t size){std::vector ret(size+size%2+2);ret[0]=ret[1]=0;ret[2]=1;for(size_t i=3;i struct ratio { T n;T d; c_ ratio(T n_,T d_):n(n_/std::gcd(n_,d_)),d(d_/std::gcd(n_,d_)){}c_ ratio(T n_):n(n_),d(1){} #define o_(o,...) c_ ratio& operato##o(const ratio& r){*this={__VA_ARGS__};return *this;} o_(r+=,n*r.d+d*r.n,r.d*d);o_(r-=,n*r.d-d*r.n,r.d*d);o_(r*=,n*r.n,r.d*d);o_(r/=,n*r.d,r.d*n); #undef o_ #define o_(o) c_ ratio operato##o(const ratio& y)const{ratio r=*this;o##=y;return r;} o_(r+);o_(r-);o_(r*);o_(r/); #undef o_ }; namespace コンセプ{ t_concept func=std::is_invocable_r_v; }; t_ c_ T segtree_id(); t_auto op,auto e_> struct segtree{std::vectorv;size_t sz;static inline T e=segtree_id(); #define SEGTREE_BODY \ c_ segtree(){}\ c_ segtree(size_t sz_):v(std::bit_ceil(sz_)*2,e),sz(std::bit_ceil(sz_)){}\ c_ segtree(std::initializer_listv){init(v);}\ t_c_ segtree(const R& v_){init(v_);}\ t_c_ void init(const R& v_){using namespace std::ranges;sz=std::bit_ceil(size(v_));v.resize(std::bit_ceil(sz*2));copy(v_,v.begin()+sz);fill(v|views::drop(size(v_)),e);auto sz_=sz/2;while(sz_!=0){for(size_t i=sz_;iauto op,auto e_>requires requires{segtree_id();} struct segtree{std::vectorv;size_t sz;c_ static T e=segtree_id();SEGTREE_BODY}; t_auto e_> c_ T segtree_id(){return e_;} t_auto e_> c_ T segtree_id(){return e_();} #undef SEGTREE_BODY int main(); #undef c_ // clang-format on } // namespace inner int main() { using namespace std; using namespace std::chrono; ios::sync_with_stdio(false); cout.precision(10); #ifdef LOCAL ifstream in("case.txt"); int n; in >> n; if (n > 0) { cin.rdbuf(in.rdbuf()); for (int i = 0; i < n; i++) { cout << "\n----test case " << i << "----" << endl; auto t0 = high_resolution_clock::now(); inner::main(); auto t1 = high_resolution_clock::now(); cout << format("\n\n{},{}", i, t1 - t0) << endl; } } else if (n < 0) { } else { inner::main(); } return 0; #else inner::main(); return 0; #endif } using namespace inner; using std::cin, std::cout; #define main inner::main #include #include #include int main() { int N, T; cin >> N >> T; std::vector A(N); for (auto& a : A) cin >> a; std::vector mins(T + 11, 1ll << 60); mins[A[0]] = 0; std::vector mins_(T + 11); for (int i = 1; i < N; i++) { for (auto& a : mins_) a = 1ll << 60; for (int j = 0; j <= T; j++) { if (mins[j] == 1ll << 60) continue; if (j + A[i] <= T) mins_[j + A[i]] = std::min(mins_[j + A[i]], mins[j] * 2); if (j * A[i] <= T) mins_[j * A[i]] = std::min(mins_[j * A[i]], mins[j] * 2 + 1); } swap(mins, mins_); } for (int i = 1; i < N; i++) { cout << (mins[T] & (1 << (N - i - 1)) ? '*' : '+'); } cout << '\n'; return 0; }