結果
問題 | No.393 2本の竹 |
ユーザー |
![]() |
提出日時 | 2016-07-29 14:50:28 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 35 ms / 1,000 ms |
コード長 | 1,804 bytes |
コンパイル時間 | 584 ms |
コンパイル使用メモリ | 59,484 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-11-08 09:27:33 |
合計ジャッジ時間 | 1,791 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
//A1~Amを昇順ソートしても答えに影響しないので、A1~Amを昇順ソートしよう。//このとき、「k人に提供可能⇔A1~Ak「全員」に提供可能」と置き換えられる。//また、A1~Akの提供先は(竹1)か(竹2)のどちらかになる。//そして、竹の長さ以下ならいくらでも切り出せる。//よって、(竹1)から (=片方の竹から) できるだけ多く切り出す方がよい。これはO(n1 * m)のDPでできる。//あとは、kを2分探索して答え。 全体で、O(d * log(m) * n1 * m) -> 10 * 6 * 10^5 * 60 … ちょっと遅い//工夫://・同じクエリにおいて、O(n1 * m)のDPテーブルは使いまわせる。//これをすると、O(d * n1 * m) -> 10 * 10^5 * 60 -> 6000万 … なんとか間に合う. (なお、kを線形探索しても間に合う)#include <iostream>#include <algorithm>using namespace std;int d;int n1, n2;int m;int a[60];bool dp[61][200001]; //dp[i][j] = a[0]~a[i-1]の部分和がjになり得るか?bool isOk(int k) {int i, sigma = 0;for (i = 0; i < k; i++) sigma += a[i];for (i = n1; i >= 0; i--) if (dp[k][i]) break;return (sigma - i <= n2);}int main() {int i, j;cin >> d;while (d--) {cin >> n1 >> n2;cin >> m;for (i = 0; i < m; i++) cin >> a[i];//準備sort(a, a + m);for (i = 0; i <= m; i++) for (int j = 0; j <= 100000; j++) dp[i][j] = false;//DPしたれ!dp[0][0] = true;for (i = 0; i < m; i++) {for (j = 0; j <= n1; j++) {//a[i]を使わないdp[i + 1][j] |= dp[i][j];//a[i]を使うdp[i + 1][j + a[i]] |= dp[i][j];}}//線形探索~♪for (int k = m; k >= 0; k--) {if (isOk(k)) {cout << k << endl;break;}}}return 0;}