結果

問題 No.2918 Divide Applicants Fairly
ユーザー rlangevin
提出日時 2024-10-12 00:28:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,059 bytes
コンパイル時間 1,402 ms
コンパイル使用メモリ 106,008 KB
実行使用メモリ 222,900 KB
最終ジャッジ日時 2024-10-12 00:28:48
合計ジャッジ時間 43,114 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 58 RE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <bitset>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> R(N);
    for (int i = 0; i < N; ++i) {
        cin >> R[i];
    }

    map<int, bitset<20000005>> pre;
    int M = 0;
    for (int r : R) M += r;
    M += 5;

    pre[0].set(M);
    
    for (int i = 0; i < N; ++i) {
        map<int, bitset<20000005>> dp;
        
        for (auto& [k, v] : pre) {
            dp[k] |= v;
            if (k == 1) {
                if (v[M + R[i]]) {
                    cout << 0 << endl;
                    return 0;
                }
            }
            if (k == -1) {
                if (v[M - R[i]]) {
                    cout << 0 << endl;
                    return 0;
                }
            }
            dp[k - 1] |= v >> R[i];
            dp[k + 1] |= v << R[i];
        }
        swap(dp, pre);
    }

    for (int i = 1; i < M; ++i) {
        if (pre[0][M + i]) {
            cout << i << endl;
            return 0;
        }
    }

    return 0;
}
0