結果

問題 No.4 おもりと天秤
ユーザー Eki1009
提出日時 2020-11-17 11:14:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,077 bytes
コンパイル時間 2,091 ms
コンパイル使用メモリ 197,936 KB
最終ジャッジ日時 2025-01-16 01:17:20
ジャッジサーバーID
(参考情報)
judge3 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
#define endl ('\n')
inline vector<int64_t> range(int64_t stop){vector<int64_t>v(stop);iota(v.begin(),v.end(),0LL);return v;}
inline vector<int64_t> range(int64_t start,int64_t stop){vector<int64_t>v(stop-start);iota(v.begin(),v.end(),start);return v;}
inline vector<int64_t> range(int64_t start,int64_t stop,int64_t step){int s=step>0?(stop-start+step-1)/step:(stop-start+step+1)/step;if(s<=0)return {};vector<int64_t>v(s);for(int i=0;i<s;++i)v[i]=i?v[i-1]+step:start;return v;}


int main(){
    int n;
    cin >> n;
    vi W(n);;
    int m = 0;
    for(auto i:range(n)){cin >> W[i];m += W[i];}
    if(m%2){cout << "impossible" << endl;return 0;}
    m /= 2;
    vi dp(m+1);
    for(auto i:range(m+1))dp[i]=0;
    dp[0] = 1;
    for(auto w:W){
        for(auto j:range(m, w-1, -1))dp[j] |= dp[j-w];
    }
    if(!dp[m])cout << "im";
    cout << "possible" << endl;
    return 0;
}
0