1855D - Earn or Unlock - CodeForces Solution

#include<iostream>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
using LL = long long;

int main() {

	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int n;
	cin >> n;
	vector<int> a(n + 1);
	vector<LL> s(n + 1);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	bitset<200001> dp;
	LL ans = a[1];
	dp.set(a[1]);
	dp.reset(0);
	for(int i = 2; i <= n; i++) {
		if (dp.test(i - 1)) {
			ans = max(ans, s[i] - (i - 1));
		}
		dp |= dp << a[i];
		dp.reset(i - 1);
	}
	for(int i = n - 1; i <= 2 * n; i++) {
		if (dp.test(i)) {
			ans = max(ans, s[n] - i);
			
		}
	}
	cout << ans << '\n';

}