結果
問題 |
No.4 おもりと天秤
|
ユーザー |
|
提出日時 | 2018-11-12 19:39:36 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 20 ms / 5,000 ms |
コード長 | 1,067 bytes |
コンパイル時間 | 1,659 ms |
コンパイル使用メモリ | 159,756 KB |
実行使用メモリ | 13,252 KB |
最終ジャッジ日時 | 2024-12-23 21:53:35 |
合計ジャッジ時間 | 2,997 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> #include <unordered_set> using namespace std; #define ll long long #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) #define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++) #define revrep(i,n) for(int (i)=(n)-1;i>=0; i--) bool dp[101][100000]; int main() { cin.tie(0); ios::sync_with_stdio(false); cout<<setprecision(std::numeric_limits<float>::max_digits10); int n; cin>>n; vector<int> ws(n+1); rep(i,n)cin>>ws[i+1]; int s = accumulate(ws.begin(),ws.end(),0); if(s%2==1) { cout << "impossible"<<endl; return 0; } memset(dp,false,sizeof(dp)); rep(i,n+1) dp[i][0] = true; repeat(i,1,n+1) { repeat(w,1,100000) { dp[i][w] = dp[i-1][w]; if(w-ws[i]>=0&&dp[i-1][w-ws[i]]) { dp[i][w] = true; } } } // rep(i,6) { // rep(w,6) { // if(dp[i][w]) cout << "true "; // else cout << "false "; // } // cout << endl; // } // cout << "s=" << s << endl; if(dp[n][s/2]) { cout << "possible" << endl; } else { cout << "impossible" << endl; } return 0; }