結果
問題 | No.15 カタログショッピング |
ユーザー | Onju |
提出日時 | 2015-02-12 22:53:51 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 657 ms / 5,000 ms |
コード長 | 1,420 bytes |
コンパイル時間 | 887 ms |
コンパイル使用メモリ | 72,488 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-09-06 00:12:40 |
合計ジャッジ時間 | 3,228 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 44 ms
4,380 KB |
testcase_06 | AC | 124 ms
4,384 KB |
testcase_07 | AC | 317 ms
4,376 KB |
testcase_08 | AC | 657 ms
4,376 KB |
testcase_09 | AC | 396 ms
4,380 KB |
コンパイルメッセージ
main.cpp: In function ‘bool compAns(const int&, int)’: main.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type] } ^
ソースコード
#include <iostream> #include <algorithm> #include <cstring> #include <climits> #include <bitset> #include <vector> #include <string> #include <sstream> #define setBit(x,b) ((x)|(1<<(b))) #define getBit(x,b) ((x)&(1<<(b))) #define N_MAX 31 #define S_MAX 310000000 #define P_MAX 10000000 using namespace std; typedef struct { int no; int P; }Goods; int N, S; Goods G[N_MAX]; vector<int> ans; int max_p[N_MAX]; bool compG(const Goods& x, const Goods& y) { return x.P > y.P; } bool compAns(const int& x, const int y) { for (int i = 1; i <= N; ++i) { if (getBit(x, i) == getBit(y, i)) continue; return getBit(x, i) > getBit(y, i); } } void DP(int t, int n, int op) { if (t == 0 && n >= N) { ans.push_back(op); return; } if (t < 0 || n >= N || max_p[n] < t) return; DP(t - G[n].P, n + 1, setBit(op, G[n].no)); DP(t, n + 1, op); } void calc() { sort(G, G + N, compG); max_p[N - 1] = G[N - 1].P; for (int i = N - 2; i >= 0; --i) { max_p[i] = max_p[i + 1] + G[i].P; } DP(S, 0, 0); sort(ans.begin(), ans.end(), compAns); } int main() { cin >> N >> S; for (int i = 0; i < N; ++i) { G[i].no = i + 1; cin >> G[i].P; } calc(); for (auto it = ans.begin(); it != ans.end(); ++it) { bool first = true; for (int i = 1; i <= N; ++i) { if (getBit(*it, i)) { if (!first) cout << ' '; cout << i; first = false; } } cout << endl; } return 0; }