結果

問題 No.506 限られたジャパリまん
ユーザー gigimegigime
提出日時 2017-04-21 22:58:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 66 ms / 2,000 ms
コード長 1,341 bytes
コンパイル時間 1,885 ms
コンパイル使用メモリ 182,784 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-28 04:10:43
合計ジャッジ時間 2,985 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;
int H,W,K,P;
vector<int> X,Y;
vector<string> name;
ll memo [100] [100];
const ll MOD = 1e9 + 7;
int bit_count(int x)
{
int res = 0;
for(;x;x -= x & -x) res++;
return res;
}
ll rec(ll y,ll x,set< pair<int,int> >& st)
{
if(st.count(make_pair(y,x))) return 0ll;
if(memo [y] [x] != -1) return memo [y] [x];
ll res = 0;
if(y) res += rec(y - 1,x,st);
if(x) res += rec(y,x - 1,st);
return memo [y] [x] = res;
}
int main()
{
cin >> H >> W >> K >> P;
X.assign(K,0);
Y.assign(K,0);
name.assign(K,"");
FOR(i,0,K){
cin >> X [i] >> Y [i] >> name [i];
}
ll mx = 0;
vector<string> ans;
FOR(i,0,1 << K) if(bit_count(i) == P){
memset(memo,-1,sizeof(memo));
memo [0] [0] = 1;
set< pair<int,int> > st;
FOR(j,0,K) if((i >> j & 1) == 0){
st.insert(make_pair(Y [j],X [j]));
}
if(chmax(mx,rec(W,H,st))){
ans.clear();
FOR(j,0,K) if(i >> j & 1){
ans.push_back(name [j]);
}
}
}
cout << mx % MOD << endl;
FOR(i,0,ans.size()){
cout << ans [i] << endl;
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0