Submission #2671762

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100 + 10;
const int M = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
const ll oo = 10000000000000000;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, ll> ii;
#define pb push_back 
#define all(c) (c).begin(),(c).end()
int n,v[N],level[N],vis[N],vs;
vi g[N];
vector<ii> E;
bool bfs(){
	vis[0]=++vs;
	queue<int> q;
	q.push(0);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0; i<g[u].size(); ++i){
			int e=g[u][i];
			int d=E[e].first;
			ll c=E[e].second;
			if(!c || vis[d]==vs)continue;
			vis[d]=vs;
			level[d]=level[u]+1;
			q.push(d);
		}
	}
	return vis[101]==vs;
}
int adj[N];
ll dfs(int u, ll fl){
	if(u==101)
		return fl;
	for(int &i=adj[u]; i<g[u].size(); ++i){
		int e=g[u][i];
		int d=E[e].first;
		ll c=E[e].second;
		if(c && level[d]==level[u]+1){
			ll cc=dfs(d, min(fl, (ll)c));
			if(cc){
				E[e].second-=cc;
				E[e^1].second+=cc;
				return cc;
			}
		}
	}
	return 0;
}
ll dinic(){
	ll flow=0;
	while(bfs()){
		memset(adj, 0, sizeof(adj));
		while(ll cc=dfs(0, oo))
			flow+=cc;
	}
	return flow;
}
void addEdge(int a, int b, ll c){
	g[a].pb(E.size());
	E.pb(ii(b,c));
	g[b].pb(E.size());
	E.pb(ii(a,0));
}
int main(){
	cin>>n;
	for(int i=1; i<=n; ++i){
		cin>>v[i];
		v[i]*=-1;
	}
	for(int i=1; i<=n; ++i)
		for(int j=i+i; j<=n; j+=i)
			addEdge(i,j,oo);
	ll allpos=0;
	for(int i=1; i<=n; ++i)
		if(v[i]>=0)
			addEdge(0,i,v[i]);
		else
			addEdge(i,101,-v[i]),allpos-=v[i];
	cout<<allpos-dinic()<<endl;
	return 0;
}

Submission Info

Judge Result