結果
問題 |
No.4 おもりと天秤
|
ユーザー |
|
提出日時 | 2018-09-29 17:11:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 934 bytes |
コンパイル時間 | 770 ms |
コンパイル使用メモリ | 85,420 KB |
最終ジャッジ日時 | 2025-01-06 14:12:02 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 TLE * 9 |
コンパイルメッセージ
main.cpp:8:11: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 8 | int solve(auto const& ws, auto& memo, int i, int w) { | ^~~~ main.cpp:8:27: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’ 8 | int solve(auto const& ws, auto& memo, int i, int w) { | ^~~~
ソースコード
#include<iostream> #include<vector> #include<map> #include<algorithm> static int const INF{100000000}; int solve(auto const& ws, auto& memo, int i, int w) { if(i == ws.size()) return 0; if(w < ws[i]) { return memo[i][w] = solve(ws, memo, i + 1, w); } int v1 = solve(ws, memo, i + 1, w); int v2 = solve(ws, memo, i + 1, w - ws[i]) + ws[i]; memo[i][w] = std::max(v1, v2); return memo[i][w]; } int main(int, char**) { int n; std::cin >> n; std::vector<int> ws(n); int sum{}; for(int i{}; i < n; ++i) { int t; std::cin >> t; ws[i] = t; sum += t; } if(sum % 2) { std::cout << "impossible" << std::endl; return 0; } sum /= 2; std::vector<std::vector<int>> memo(n + 1, std::vector(sum + 1, 0)); std::sort(begin(ws), end(ws), std::greater<int>()); int v = solve(ws, memo, 0, sum); std::cout << (sum == v ? "possible" : "impossible") << std::endl; return 0; }