結果

問題 No.4 おもりと天秤
ユーザー dazy
提出日時 2017-11-25 02:57:02
言語 C++11(廃止可能性あり)
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 986 bytes
コンパイル時間 573 ms
コンパイル使用メモリ 56,556 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-27 09:01:56
合計ジャッジ時間 1,168 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 15 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
using namespace std;

#define fastcin {\
    cin.tie(0);\
    ios::sync_with_stdio(false);\
}
#define rep(i, a, b) for(int i = a; i < b; i++)
#define scan(x) cin >> x
#define print(x) cout << x << "\n"


int main() {
    fastcin;

    int n;
    scan(n);
    int sum = 0, w[n+1];
    rep(i, 1, n+1) {
        scan(w[i]);
        sum += w[i];
    }
    if (!(sum & 0x01)) {
        int half = sum / 2;
        bool dp[n + 1][half + 1];
        rep(i, 1, n+1) rep(j, 1, half+1) dp[i][j] = false;
        dp[1][1] = true;
        rep(i, 1, n) {
            rep(j, 1, half + 1) {
                if (dp[i][j]) {
                    if (j == 1) dp[i + 1][1] = true;
                    if (j + w[i] < half) dp[i + 1][j + w[i]] = true;
                    else if (j + w[i] == half) {
                        print("possible");
                        exit(0);
                    }
                }
            }
        }
    }

    print("impossible");
    return 0;
}
0