Submission #4016311

---

Source Code Expand

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

template <typename T>
vector<T> divisor(T N) {
	vector<T> res;
	for (T i = 1; i * i <= N; i++) {
		if (N % i == 0) {
			res.push_back(i);
			if (N != i * i) res.push_back(N / i);
		}
	}
	sort(res.begin(), res.end());
	return res;
}

int main()
{
	int N;
	cin >> N;
	vector<ll> a(N + 1);
	for (int i = 0; i < N; i++) {
		cin >> a[i + 1];
	}
	ll res = accumulate(a.begin(), a.end(), 0LL);
	for (int i = N; i >= 1; i--) {
		auto d = divisor(i);
		int n = d.size();
		reverse(d.begin(), d.end());
		for (int j = 0; j < (1 << n); j++) {
			int s = j;
			for (int k = n - 1; k >= 0; k--) if ((1 << k) & s) {
				for (int l = 0; l < k; l++) if (d[l] % d[k] == 0) {
					s &= (1 << n) - 1 - (1 << l);
				}
			}
			auto t = a;
			ll cost = 0;
			for (int k = 0; k < n; k++) if ((1 << k) & s) {
				for (int l = d[k]; l <= N; l += d[k]) {
					cost += t[l];
					t[l] = 0;
				}
			}
			if (cost < 0) {
				res -= cost;
				a = t;
			}
		}
	}
	cout << res << endl;
	return 0;
}

Submission Info

Judge Result