結果

問題 No.506 限られたジャパリまん
ユーザー masamasa
提出日時 2017-04-22 13:39:07
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 1,809 bytes
コンパイル時間 786 ms
コンパイル使用メモリ 79,484 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-10 12:53:28
合計ジャッジ時間 1,890 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <climits>

using namespace std;
const long long inf = 9e18;
const int mod = 1e9 + 7;

int h, w, k, p;
vector<int> x, y;

void check() {
	w = 32;
	h = 32;
	vector<vector<long long>> board(h+1, vector<long long>(w+1, 0));

	for (int i = 0; i <= h; i++) {
		board[i][0] = 1;
	}
	for (int i = 0; i <= w; i++) {
		board[0][1] = 1;
	}

	for (int i = 1; i <= h; i++) {
	for (int j = 1; j <= w; j++) {
		board[i][j] += board[i-1][j] + board[i][j - 1];
		printf("%2d %2d: %20llu\n", i, j, board[i][j]);
	}}
}

long long calc(int ok_bits) {
	// 東西方向にHメートル、南北方向にWメートル
	vector<vector<long long>> board(w+2, vector<long long>(h+2, 0));
	board[0][0] = 1;

	// vector<string> aaa(w+1, string(h+1, '.'));

	for (int i = 0; i < k; i++) {
		if ((ok_bits >> i) & 1) {
			continue;
		}
		board[y[i]][x[i]] = -inf;
		// aaa[y[i]][x[i]] = 'x';
	}

	for (int i = 0; i <= w; i++) {
	for (int j = 0; j <= h; j++) {
		if (board[i][j] > 0) {
			board[i+1][j] += board[i][j];
			board[i][j+1] += board[i][j];
		}
	}}

	// for (auto s : aaa) {
	// 	cout << s << endl;
	// }

	return max(board[w][h], 0LL);

}

int main() {
	cin >> h >> w >> k >> p;

	x.assign(k, 0);
	y.assign(k, 0);
	vector<string> name(k);
	for (int i = 0; i < k; i++) {
		cin >> x[i] >> y[i] >> name[i];
	}

	long long ans = 0;
	int store = 0;
	for (int i = 0; i < (1 << k); i++) {
		if (__builtin_popcount(i) != p) {
			continue;
		}
		auto val = calc(i);
// printf("%5d: %20lld, %20lld\n", i, val, val % mod);
		if (val > ans) {
			ans = val;
			store = i;
		}
	}

	ans %= mod;
	cout << ans << endl;
	for (int i = 0; i < k; i++) {
		if ((store >> i) & 1) {
			cout << name[i] << endl;
		}
	}
	return 0;
}
0