結果

問題 No.506 限られたジャパリまん
コンテスト
ユーザー legendcn
提出日時 2025-01-28 23:26:04
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 1,151 bytes
コンパイル時間 1,838 ms
コンパイル使用メモリ 167,332 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-28 23:26:08
合計ジャッジ時間 2,576 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:21:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   21 |         scanf ("%lld%lld%lld%lld", &n, &m, &k, &p);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 55, mod = 1e9 + 7;

int n, m, k, p;
struct node
{
	int x, y;
	string nm;
} a[N];
int f[N][N];
signed main ()
{
//	freopen ("kart.in", "r", stdin); freopen ("kart.out", "w", stdout);
	scanf ("%lld%lld%lld%lld", &n, &m, &k, &p); 
	for (int i = 0; i < k; i ++ ) cin >> a[i].x >> a[i].y >> a[i].nm;
	int ans = 0; vector <int> res;
	for (int s = 0; s < (1 << k); s ++ )
	{
		if (__builtin_popcount (s) != p) continue;
		memset (f, 0, sizeof f);
		vector <int> chs;
		for (int i = 0; i < k; i ++ )
		{
			if (!(s >> i & 1)) f[a[i].x][a[i].y] = -1;
			else chs.push_back (i);
		}
		f[0][0] = 1;
		for (int i = 0; i <= n + 1; i ++ )
		{
			for (int j = 0; j <= m + 1; j ++ )
			{
				if (f[i][j] == -1) continue;
				if (i >= 1 && ~f[i - 1][j]) f[i][j] += f[i - 1][j];
				if (j >= 1 && ~f[i][j - 1]) f[i][j] += f[i][j - 1];
			}
		}
		if (ans < f[n][m]) ans = f[n][m], res = chs;
	}
	printf ("%lld\n", ans % mod);
	for (auto x : res) cout << a[x].nm << "\n";
	return 0;
}
0