#170074 (C++11) No.10 ＋か×か

• 問題: No.10 ＋か×か
• ユーザー: myanta
• 提出日時: 2017-04-30 21:29:43
• 言語: C++11 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 13 ms / 5,000 ms
• コード長: 834 bytes
• コンパイル時間: 268 ms
• コンパイル使用メモリ: 62,596 KB
• 実行使用メモリ: 23,040 KB
• 最終ジャッジ日時: 2026-07-19 00:10:03
• 合計ジャッジ時間: 1,625 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
other	AC * 13

ソースコード

#include<cstdio>
#include<vector>


using namespace std;


int main(void)
{
	int n, t, i, j, s;
	vector<int> a;
	vector<vector<int> > b;

	while(scanf("%d%d", &n, &t)==2)
	{
		b.clear();
		a.resize(n);
		b.resize(n);
		for(i=0;i<b.size();i++)
		{
			b[i].resize(t+1);
		}
		for(i=0;i<n;i++)
		{
			scanf("%d", &a[i]);
		}

		b[n-1][t]=1;
		for(i=n-1;i>0;i--)
		{
			for(j=0;j<=t;j++)
			{
				if(b[i][j])
				{
					if(j-a[i]>0) b[i-1][j-a[i]]=1;
					if(j%a[i]==0) b[i-1][j/a[i]]=1;
				}
			}
		}
/*
for(i=0;i<b.size();i++)
{
	for(j=0;j<=t;j++) printf("%d", b[i][j]);
	printf("\n");
}
*/
		s=a[0];
		for(i=1;i<n;i++)
		{
			if(s+a[i]<=t && b[i][s+a[i]])
			{
				s+=a[i];
				printf("+");
				continue;
			}
			if(s*a[i]<=t && b[i][s*a[i]])
			{
				s*=a[i];
				printf("*");
				continue;
			}
		}
		printf("\n");
	}

	return 0;
}