Submission #5542047

---

Source Code Expand

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>  
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000000000000000000000001
#define LONG_INF 10000000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD  998244353
#define REP(i,n) for(long long i = 0;i < n;++i)
long long flowing[200][200] = {};
vector<int> kouho[200];
int visited[200] = {};
int finding(long long now,long long back,long long now_max) {
	if (now == 101) {
		return now_max;
	}
	for (int i = 0; i < kouho[now].size(); ++i) {
		if (kouho[now][i] != back) {
			if (visited[kouho[now][i]] == 0&&flowing[now][kouho[now][i]] != 0) {
				visited[kouho[now][i]] = 1;
				int geko = finding(kouho[now][i], now, min(now_max, flowing[now][kouho[now][i]]));
				if (geko != 0) {
					flowing[now][kouho[now][i]] -= geko;
					flowing[kouho[now][i]][now] += geko;
					return geko;
				}
			}
		}
	}
	return 0;
}
int main() {
	int n;
	cin >> n;
	long long ans = 0;
	REP(i, n) {
		int b;
		cin >> b;
		if (b <= 0) {
			flowing[0][i + 1] = -b;
			kouho[0].push_back(i + 1);
			ans += b;
		}
		else {
			flowing[i + 1][101] = b;
			kouho[i + 1].push_back(101);
			ans += b;
		}
	}
	for (int i = 1; i <= 100; ++i) {
		for (int q = 2; i * q <= 100; ++q) {
			kouho[i].push_back(i*q);
			kouho[q * i].push_back(i);
			flowing[i][i * q] = LONG_INF;
		}
	}
	visited[0] = 1;
	while (finding(0,-1,LONG_INF)) {
		REP(i, 200) {
			visited[i] = 0;
		}
		visited[0] = 1;
	}
	for (int i = 1; i <= 101; ++i) {
		ans += flowing[0][i];
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result