結果

問題 No.506 限られたジャパリまん
コンテスト
ユーザー bal4u
提出日時 2019-09-06 05:59:43
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,704 bytes
コンパイル時間 551 ms
コンパイル使用メモリ 31,872 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-28 04:21:58
合計ジャッジ時間 1,369 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:11:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
   11 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:17:24: note: in expansion of macro 'gc'
   17 |         int n = 0, c = gc();
      |                        ^~

ソースコード

diff # 

// yukicoder: 506 限られたジャパリまん
// 2019.9.6 bal4u

#include <stdio.h>
#include <string.h>

typedef long long ll;

//// 高速入力
#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

void ins(char *s) { // 文字列の入力　スペース以下の文字で入力終了
	do *s = gc();
	while (*s++ > ' ');
	*(s-1) = 0;
}

//// 2^16までのビット数を数える popcount()と同等？
int bitcount(int x) {
	x = ((x & 0xAAAAAA) >>  1) + (x & 0x555555);
	x = ((x & 0xCCCCCC) >>  2) + (x & 0x333333);
	x = ((x & 0xF0F0F0) >>  4) + (x & 0x0F0F0F);
	x = ((x & 0x00FF00) >>  8) + (x & 0xFF00FF);
	return x;
}

#define MOD 1000000007
int H, W, K, P;
int rr[17], cc[17]; char name[17][13];
char map[35][35];
ll dp[35][35];
	
int main()
{
	int i, r, c;
	ll max; int path;
	
	H = in(), W = in(), K = in(), P = in();
	for (i = 0; i < K; i++) rr[i] = in(), cc[i] = in(), ins(name[i]);
	
	max = 0;
	int lim = 1 << K; for (i = 0; i < lim; i++) if (bitcount(i) == P) {
		memset(map, 1, sizeof(map));
		for (int j = 0; j < K; j++) if (!((i >> j) & 1)) map[rr[j]][cc[j]] = 0; // 通れないとこ
		
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for (r = 1; r <= H; r++) if (map[r][0]) dp[r][0] = dp[r-1][0];
		for (c = 1; c <= W; c++) if (map[0][c]) dp[0][c] = dp[0][c-1];
		for (r = 1; r <= H; r++) for (c = 1; c <= W; c++) if (map[r][c])
			dp[r][c] = dp[r-1][c] + dp[r][c-1];
		
		if (dp[H][W] > max) max = dp[H][W], path = i;
	}
	printf("%d\n", max % MOD);
	if (max) for (i = 0; i < K; i++) if (path & (1 << i)) puts(name[i]);
	return 0;
}
0