結果
問題 | No.4 おもりと天秤 |
ユーザー |
|
提出日時 | 2025-01-27 13:31:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,042 bytes |
コンパイル時間 | 4,161 ms |
コンパイル使用メモリ | 319,068 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-27 13:31:29 |
合計ジャッジ時間 | 5,241 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 WA * 2 |
ソースコード
typedef long long ll;typedef long double ld;#include <bits/stdc++.h>using namespace std;// #define int long long#include <ext/pb_ds/assoc_container.hpp>using namespace __gnu_pbds;template<typename T>using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;// std::cout << *s.find_by_order(1) << std::endl; // 2signed main(){// これがないと落ちることがあるios_base::sync_with_stdio(false);cin.tie(0);ll n;cin >> n;vector<ll> w(n);ll sum = 0;for (ll i = 0; i < n; i++){cin >> w[i];sum += w[i];}if(sum%2==1){cout << "impossible" << endl;return 0;}vector<vector<bool>> dp(n+1, vector<bool>(sum/2+1));dp[0][0] = true;for (ll i = 0; i < n; i++){for (ll j = 0; j <= sum/2; j++){dp[i+1][j] = dp[i][j] || dp[i][j-w[i]];}}if(dp[n][sum/2]){cout << "possible" << endl;}else{cout << "impossible" << endl;}}