結果

問題 No.10 ＋か×か
ユーザー A63635985A63635985
提出日時 2018-03-03 22:49:13
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,549 bytes
コンパイル時間 563 ms
コンパイル使用メモリ 56,828 KB
実行使用メモリ 8,704 KB
最終ジャッジ日時 2024-07-04 23:39:13
合計ジャッジ時間 1,259 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
using namespace std;
struct Struct{
        bool plus,times;
};
int main(){
        int N,total;
        cin >> N >> total;
        int number[60];
        for(int i=0 ; i<N ; i++ )
                cin >> number[i];
        bool dp[51][100001];
        Struct ope[100001];
        for(int i=0 ; i<=total ; i++ )
                ope[i].plus=ope[i].times=false;
        dp[0][number[0]]=true;
        dp[1][number[0]]=true;
        for(int i=1 ; i<=N ; i++ ){
                for(int j=1 ; j<=total ; j++ ){
                        dp[i][j]|=dp[i-1][j];
                        if(j%number[i-1]==0){
                                dp[i][j]|=dp[i-1][j/number[i-1]];
                                ope[j].times|=dp[i-1][j/number[i-1]];
                        }
                        if(number[i-1]<=j){
                                dp[i][j]|=dp[i-1][j-number[i-1]];
                                ope[j].plus|=dp[i-1][j-number[i-1]];
                        }
                }
        }
        string str="";
        int now=N-1;
        int i=total;
        for(int now=(N-1) ; now>=0 ; now-- ){
                if(ope[i].plus && (i-number[now]!=0&&now!=0)){
                        i-=number[now];
                        str+='+';
                }else if(ope[i].times){
                        i/=number[now];
                        str+='*';
                }
        }
        string ans="";
        for(int i=str.size()-2 ; i>=0 ; i-- )
                ans+=str[i];
        cout << ans << endl;
        return 0;
}
0