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? We do N operations of shifting W elements. But bitset works as a long binary numbers(which constructs of a many 32bit integers. So we don't shift W numbers, we shift only W/32. this is why it work's so fast

But this solution runs in 1s, which is too much. How to improve out improvement? Add some useful pragmas:

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

Now it runs in ~700ms

P.S This was our first ever problem created on polygon, so we failed it a little with bad tests. Sorry, we will improve outself for the future!

Also thanks for a great callback!