結果

問題 No.506 限られたジャパリまん
ユーザー myantamyanta
提出日時 2017-04-22 00:55:33
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 1,427 bytes
コンパイル時間 573 ms
コンパイル使用メモリ 55,532 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-10 12:53:06
合計ジャッジ時間 1,539 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,384 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 12 ms
4,376 KB
testcase_09 AC 6 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 11 ms
4,376 KB
testcase_12 AC 6 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 12 ms
4,376 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 3 ms
4,380 KB
testcase_20 AC 3 ms
4,384 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 4 ms
4,376 KB
testcase_23 AC 3 ms
4,380 KB
testcase_24 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<vector>
#include<algorithm>


using namespace std;


typedef long long ll;

struct fre_t
{
	int x, y;
	char name[20];
};


int w, h, k, p;
vector<vector<ll> > field;
vector<fre_t> fre;


void field_init(int w, int h)
{
	field.clear();
	field.resize(h+1);
	for(int y=0;y<=h;y++)
	{
		field[y].resize(w+1);
	}
}


void solve(ll& result, vector<int>& result_item, vector<int>& item)
{
	do
	{
		field_init(w, h);
		field[0][0]=1;
		for(int i=0;i<k;i++)
		{
			if(item[i]==0) field[fre[i].y][fre[i].x]=-1;
		}
		for(int y=0;y<=h;y++)
		{
			for(int x=0;x<=w;x++)
			{
				if(field[y][x]<0) continue;

				if(x>0 && field[y  ][x-1]>=0) field[y][x]+=field[y  ][x-1];
				if(y>0 && field[y-1][x  ]>=0) field[y][x]+=field[y-1][x  ];
			}
		}
		if(result<field[h][w])
		{
			result=field[h][w];
			result_item=item;
		}
	}
	while(next_permutation(item.begin(), item.end()));
}


int main(void)
{
	ll result;
	vector<int> result_item;
	vector<int> item;

	while(scanf("%d%d%d%d", &w, &h, &k, &p)==4)
	{
		fre.resize(k);
		item.resize(k);
		for(int i=0;i<k;i++)
		{
			scanf("%d%d%s", &fre[i].x, &fre[i].y, fre[i].name);
		}
		for(int i=0;i<k;i++)
		{
			item[i]=((k-i)<=p);
		}
		result=0;
		result_item=item;
		solve(result, result_item, item);

		printf("%lld\n", result%1000000007);
		if(result>0)
		{
			for(int i=0;i<k;i++)
			{
				if(result_item[i]) printf("%s\n", fre[i].name);
			}
		}
	}

	return 0;
}
0