#167782 (C++11) No.506 限られたジャパリまん

• 問題: No.506 限られたジャパリまん
• ユーザー: ukuku09
• 提出日時: 2017-04-21 23:29:08
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 605 ms / 2,000 ms
• コード長: 1,570 bytes
• コンパイル時間: 1,303 ms
• コンパイル使用メモリ: 146,388 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-09-10 12:52:33
• 合計ジャッジ時間: 5,362 ms
• ジャッジサーバーID （参考情報）: judge13 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,380 KB
testcase_01	AC	2 ms; 4,380 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	1 ms; 4,376 KB
testcase_04	AC	605 ms; 4,380 KB
testcase_05	AC	598 ms; 4,380 KB
testcase_06	AC	2 ms; 4,380 KB
testcase_07	AC	2 ms; 4,380 KB
testcase_08	AC	84 ms; 4,376 KB
testcase_09	AC	20 ms; 4,376 KB
testcase_10	AC	2 ms; 4,376 KB
testcase_11	AC	245 ms; 4,380 KB
testcase_12	AC	90 ms; 4,380 KB
testcase_13	AC	1 ms; 4,376 KB
testcase_14	AC	3 ms; 4,376 KB
testcase_15	AC	2 ms; 4,376 KB
testcase_16	AC	63 ms; 4,376 KB
testcase_17	AC	45 ms; 4,376 KB
testcase_18	AC	115 ms; 4,376 KB
testcase_19	AC	5 ms; 4,376 KB
testcase_20	AC	291 ms; 4,376 KB
testcase_21	AC	287 ms; 4,376 KB
testcase_22	AC	546 ms; 4,380 KB
testcase_23	AC	139 ms; 4,380 KB
testcase_24	AC	2 ms; 4,380 KB

ソースコード

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int H, W, K, P;
int x[20], y[20];
string n[20];
int mas[33][33];

int dx[] = {1, 0};
int dy[] = {0, 1};

unsigned int dp[33][33];

unsigned int solve(int mx, int my, int bit) {
  if(mx == H && my == W) return 1;
  if(mx < 0 || H < mx || my < 0 || W < my) return 0;
  unsigned int& res = dp[mx][my];
  if(~res) return res;
  res = 0;
  rep(i, 2) {
    int nx = mx + dx[i], ny = my + dy[i];
    int id = mas[ny][nx];
    if(id == -1 || (bit>>id)&1) {
      res += solve(nx, ny, bit);
    }
  }
  return res;
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> H >> W >> K >> P;
  memset(mas, -1, sizeof(mas));
  rep(i, K) {
    cin >> x[i] >> y[i] >> n[i];
    mas[y[i]][x[i]] = i;
  }
  unsigned int ans = 0, bit = 0;
  rep(i, 1<<K) {
    if(__builtin_popcount(i) > P) continue;
    memset(dp, -1, sizeof(dp));
    unsigned int temp = solve(0, 0, i);
    if(temp > ans) {
      ans = temp;
      bit = i;
    }
  }
  cout << ans%mod << endl;
  rep(i, K) {
    if((bit>>i)&1) cout << n[i] << endl;
  }

  return 0;
}