結果

問題 No.10 ＋か×か
ユーザー codershifthcodershifth
提出日時 2015-07-12 18:17:27
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,703 bytes
コンパイル時間 1,530 ms
コンパイル使用メモリ 156,788 KB
実行使用メモリ 8,760 KB
最終ジャッジ日時 2023-09-22 14:20:19
合計ジャッジ時間 8,203 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
8,760 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


class AddOrMul {
public:
    void solve(void) {
            int N, Total;
            cin>>N>>Total;
            vector<int> A(N);
            REP(i, N)
                cin>>A[i];

            vector<string> ans;
            // 全探索 + 枝刈り
            function<void(int sum, int i, const string &str)> dfs = [&](int sum, int i, const string &str) {
                if (i == N)
                {
                    if (sum == Total)
                        ans.push_back(str);
                    return;
                }
                if (sum+A[i] <= Total)
                    dfs(sum+A[i], i+1, str+"+");
                if (sum*A[i] <= Total)
                    dfs(sum*A[i], i+1, str+"*");
                return;
            };
            dfs(A[0], 1, "");
            // 通常の辞書式順序とは違うので自前でやる
            sort(RANGE(ans), [](const string &a, const string &b){
                    REP(i, a.length())
                    {
                        if (a[i] == b[i])
                            continue;
                        if (a[i] == '+')
                            return true;
                        return false;
                    }
                    return false;
                });
            cout<<ans[0]<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new AddOrMul();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0