結果

問題 No.393 2本の竹
ユーザー startcppstartcpp
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

//A1AmA1Am
//k⇔A1Ak
//A1Ak(1)(2)
//
//(1) (=) O(n1 * m)DP
//k 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0