Submission #25172730

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
constexpr int Inf = 2000000000;
constexpr long long INF= 2000000000000000000;
 
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }

template<typename T,typename U>
T modpow(T N, U P, T M = -1){
    if(P < 0) return 0;
    T ret = 1;
    if(M != -1) ret %= M;
    while(P) {
        if(P & 1) {
            if(M == -1) ret *= N;
            else ret = ret * N % M;
        }
        P /= 2;
        if(M == -1) N *= N;
        else N = N * N % M;
    }
    return ret;
}
 
long long MOD = 998244353;

template<typename T>
class SegmentTree {
    int N;
    const T def;
    std::vector<T> dat;
    std::function<T(T,T)> operation_;
    std::function<T(T,T)> update_;

public:
    SegmentTree(int n,T e,std::function<T(T,T)> operation,std::function<T(T,T)> update): def(e),operation_(operation),update_(update) {
        int n_ = 1;
        while(n > n_) n_ *= 2;
        N = n_;
        dat = std::vector<T>(2 * N,def);
    }

    void set(int i,T x) { dat[i + N] = x;}
    void build() {
        for (int i = N - 1; i >= 1; i--){
            dat[i] = operation_(dat[i * 2],dat[i * 2 + 1]);
        }
    }

    void update(int i,T x) {
        i += N;
        dat[i] = update_(dat[i],x);
        while(i > 1) {
            i /= 2;
            dat[i] = operation_(dat[i * 2],dat[i * 2 + 1]);
        }
    }

    T query(int a,int b) {
        int l = a + N;
        int r = b + N;
        T left_fold = def;
        T right_fold = def;
        while(l < r) {
            if(l & 1) left_fold = operation_(left_fold,dat[l++]);
            if(r & 1) right_fold = operation_(dat[--r],right_fold);
            l >>= 1;
            r >>= 1;
        }
        return operation_(left_fold,right_fold);
    }

    T operator[](int i) {return dat[i + N];}
};

int main() {
    int N,K;
    cin >> N >> K;
    vector<int> vec(N);
    for(auto& x : vec) cin >> x;
    vector<vector<bool>> dp(N + 1,vector<bool>(K));
    vector<vector<bool>> dp2(N + 2,vector<bool>(K));
    dp[0][0] = true;
    dp2[N + 1][0] = true;
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < K;j++) {
            dp[i + 1][j] = (dp[i + 1][j] | dp[i][j]);
            if(j >= vec[i]) {
                dp[i + 1][j] = (dp[i + 1][j] | dp[i][j - vec[i]]);
            }
        }
    }
    for(int i = N + 1;i >= 2;i--) {
        for(int j = 0;j < K;j++) {
            dp2[i - 1][j] = (dp2[i - 1][j] | dp2[i][j]);
            if(j >= vec[i - 2]) {
                dp2[i - 1][j] = (dp2[i - 1][j] | dp2[i][j - vec[i - 2]]);
            }
        }
    }

    int ret = 0;
    for(int i = 0;i < N;i++) {
        SegmentTree<bool> seg(K,false,
                                [](bool a,bool b) {return a || b;},
                                [](bool a,bool b) {return b;});
        for(int j = 0;j < K;j++) {
            seg.set(j,dp[i][j]);
        }
        seg.build();
        bool res = false;
        for(int j = 0;j < K;j++) {
            if(dp2[i + 2][j]) {
                if(seg.query(max(K - vec[i] - j,0),K - j)) res = true;
            }
        }
        if(!res) ret++;
    }
    cout << ret << endl;
}

Submission Info

Compile Error

./Main.cpp: In lambda function:
./Main.cpp:107:41: warning: unused parameter ‘a’ [-Wunused-parameter]
  107 |                                 [](bool a,bool b) {return b;});
      |                                    ~~~~~^

Judge Result