結果
問題 | No.506 限られたジャパリまん |
ユーザー | tnakao0123 |
提出日時 | 2017-04-22 01:31:19 |
言語 | C++11 (gcc 13.3.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,809 bytes |
コンパイル時間 | 1,011 ms |
コンパイル使用メモリ | 85,156 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-28 04:15:16 |
合計ジャッジ時間 | 3,236 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | RE | - |
testcase_08 | WA | - |
testcase_09 | AC | 7 ms
6,940 KB |
testcase_10 | WA | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | AC | 2 ms
6,948 KB |
testcase_14 | WA | - |
testcase_15 | AC | 2 ms
6,948 KB |
testcase_16 | WA | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | WA | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | AC | 2 ms
6,940 KB |
ソースコード
/* -*- coding: utf-8 -*-** 506.cc: No.506 限られたジャパリまん - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_H = 16;const int MAX_W = 16;const int MAX_K = 15;const int KBITS = 1 << MAX_K;const int MOD = 1000000007;/* typedef */typedef long long ll;typedef vector<int> vi;typedef queue<int> qi;typedef pair<int,int> pii;/* global variables */ll dp[MAX_H + 1][MAX_W + 1];int xs[MAX_K], ys[MAX_K], bnums[KBITS];string nms[MAX_K];/* subroutines *//* main */int main() {int h, w, k, p;cin >> h >> w >> k >> p;int kbits = 1 << k;for (int i = 0; i < k; i++) cin >> xs[i] >> ys[i] >> nms[i];bnums[0] = 0;for (int bits = 1, msb = 1; bits < kbits; bits++) {if ((msb << 1) <= bits) msb <<= 1;bnums[bits] = bnums[bits ^ msb] + 1;}ll maxdp = -1;int maxbits = 0;for (int bits = 0; bits < kbits; bits++) {if (bnums[bits] > p) continue;memset(dp, 0, sizeof(dp));dp[0][0] = 1;for (int i = 0, bi = 1; i < k; i++, bi <<= 1)if (! (bits & bi)) dp[xs[i]][ys[i]] = -1;for (int x = 0; x <= h; x++)for (int y = 0; y <= w; y++)if (dp[x][y] >= 0) {if (x < h && dp[x + 1][y] >= 0) dp[x + 1][y] += dp[x][y];if (y < w && dp[x][y + 1] >= 0) dp[x][y + 1] += dp[x][y];}if (maxdp < dp[h][w]) maxdp = dp[h][w], maxbits = bits;}printf("%lld\n", maxdp % MOD);for (int i = 0, bi = 1; i < k; i++, bi <<= 1)if (maxbits & bi) puts(nms[i].c_str());return 0;}