Blog entries - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	nor	150

Python 3 has unlimited size integers, which can function as dynamic size bitsets when doing bitwise operations. Python is still about 3x slower than C++ bitsets with no pragmas and 10x slower than C++ with avx2+O3 pragmas. However, the Python integers have dynamic size, so there some potential of making a problem that requires dynamic bitsets purely to mess with people who use C++ standard library bitsets.

Anyways, here's some simple code I wrote in Python for https://ecna22.kattis.com/problems/amusicalquestion. It is AC in 0.16s.

Code

c, n = map(int, input().split())
songs = [int(i) for i in input().split()]

mask = (1 << (c + 1)) - 1


valid = [0 for _ in range(c + 1)]
valid[0] = 1

for s in songs:
    if s <= c:
        for i in range(c, s - 1, -1):
            valid[i] = (valid[i] | (valid[i] << s) | valid[i - s]) & mask
        for i in range(s - 1, -1, -1):
            valid[i] = (valid[i] | (valid[i] << s)) & mask

best = -1
bc2 = -1
bc1 = -1

for c2 in range(c + 1):
    c1 = valid[c2].bit_length() - 1
    if c1 != -1 and best <= c1 + c2 and c2 <= c1:
        best = c1 + c2
        bc1 = c1
        bc2 = c2
print(bc1, bc2)

Full text and comments »

jzhe727's blog