結果

問題 No.4 おもりと天秤
コンテスト
ユーザー なお
提出日時 2014-10-02 19:32:05
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 810 bytes
コンパイル時間 650 ms
コンパイル使用メモリ 56,204 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-31 08:17:20
合計ジャッジ時間 1,660 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstring>
using namespace std;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define RREP(i, n)          for(int(i)=(n)-1;(i)>=0;--(i))

const int MAXN = 100, MAXW = 100;
const int MAXSUMW = MAXN * MAXW / 2;

int main(){
    int N, W;
    cin >> N;
    if(N < 2 || N > MAXN){ cerr << N << endl; };

    int sum = 0;
    bool dp[MAXSUMW+1];
    memset(dp,0,sizeof(dp));
    dp[0] = true;

    REP(i,N){
        cin >> W;
        if(W < 1 || W > MAXW){ cerr << W << endl; };
        RREP(i,sum+1){
            if(!dp[i]) continue;
            if(i+W > MAXSUMW) continue;
            dp[i+W] = true;
        }
        sum += W;
    }
    if(sum % 2 || !dp[sum/2]){
        cout << "impossible" << endl;
    } else {
        cout << "possible" << endl;
    }
    return 0;
}
0