Hello codeforces! Try to solve both of the problems from https://codeforces.me/contestInvitation/fcf424afaf5b7a5d01aebf1a908d6ef3589e4fb3. good luck

Solution:

This is a simple dp problem(very simple), but with a high constraints. Standard knapsack runtime is O(NW), but we can optimize it to run in O(NW/32) using bitset.

#include<bits/stdc++.h>
using namespace std;

const int N=2e5;
const int W=2e5;
bitset<W>b;
 
signed main(){
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,w;
    scanf("%d %d",&n,&w);
    b[0]=1;
    while(n--){
        int a;
        scanf("%d",&a);
        b|=(b<<a);
    }
    if(b[w])printf("YES\n");
    else printf("NO\n");
}

How does it work? b[k] contains 0, if it's not possible to get sum k, and 1, if it's possible.

At start, we set b[0] to 1(because we can get sum 0). Next, for each item we left-shift out bitset by a[i]. new_b=b<<a[i] After this move, new bitset contains information about what can we get if we will take current item, but it ignores all previous moves(when we didn't take current item). To fix this, we need to connect two bitsets in one using bitwise or. new_new_b=new_b|b

To do this fast, we just write b|=(b<<a)

Why this works fast? in standard approach, we create array bool dp[n][w], and we do O(NW) operations with bool type, which has size of 4bytes on most systems.