#297644 (C++14) No.10 ＋か×か

• 問題: No.10 ＋か×か
• ユーザー: face4
• 提出日時: 2018-11-12 09:10:42
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 10 ms / 5,000 ms
• コード長: 595 bytes
• コンパイル時間: 472 ms
• コンパイル使用メモリ: 64,884 KB
• 実行使用メモリ: 8,608 KB
• 最終ジャッジ日時: 2024-05-08 11:57:18
• 合計ジャッジ時間: 1,048 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	5 ms; 8,464 KB
testcase_01	AC	3 ms; 8,304 KB
testcase_02	AC	3 ms; 8,588 KB
testcase_03	AC	10 ms; 8,424 KB
testcase_04	AC	10 ms; 8,428 KB
testcase_05	AC	9 ms; 8,532 KB
testcase_06	AC	9 ms; 8,388 KB
testcase_07	AC	9 ms; 8,504 KB
testcase_08	AC	6 ms; 8,468 KB
testcase_09	AC	6 ms; 8,608 KB
testcase_10	AC	4 ms; 8,308 KB
testcase_11	AC	4 ms; 8,400 KB

ソースコード

// coding on smartphone
#include<iostream>
using namespace std;

int main(){
	int n, tot, a[51];
	bool dp[51][100001] = {};
	
	cin >> n >> tot;
	for(int i = n-1; i >= 0; i--)	cin >> a[i];
	
	dp[0][tot] = true;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 100001; j++){
			if(!dp[i][j])	continue;
			if(j-a[i] >= 0)	dp[i+1][j-a[i]] = true;
			if(j%a[i] == 0)	dp[i+1][j/a[i]] = true;
		}
	}
	
	int val = a[n-1], pos = n-2;
	while(pos >= 0){
		if(dp[pos][val + a[pos]]){
			val += a[pos];
			cout << "+";
		}else{
			val *= a[pos];
			cout << "*";
		}
		pos--;
	}
	cout << endl;
	
	return 0;
}