Problem:
 Score : 700 points    Problem Statement We have N gemstones labeled 1 through N .  You can perform the following operation any number of times (possibly zero).   Select a positive integer x , and smash all the gems labeled with multiples of x .   Then, for each i , if the gem labeled i remains without getting smashed, you will receive a_i yen (the currency of Japan).
However, a_i may be negative, in which case you will be charged money.  By optimally performing the operation, how much yen can you earn?      Constraints  All input values are integers.  1 \leq N \leq 100  |a_i| \leq 10^9         Input Input is given from Standard Input in the following format:  N  a_1  a_2  ...  a_N       Output Print the maximum amount of money that can be earned.        Sample Input 1 6
1 2 -6 4 5 3      Sample Output 1 12  It is optimal to smash Gem 3 and 6 .       Sample Input 2 6
100 -100 -100 -100 100 -100      Sample Output 2 200       Sample Input 3 5
-1 -2 -3 -4 -5      Sample Output 3 0  It is optimal to smash all the gems.       Sample Input 4 2
-1000 100000      Sample Output 4 99000

Solution (Python):
from collections import deque
 
 
class Dinic:
    def __init__(self, n: int):
        """頂点数をnとする"""
        self.INF = float("inf")
        self.n = n
        self.graph = [[] for _ in range(n)]
 
    def add_edge(self, _from: int, to: int, capacity: int):
        """残余グラフを構築
        1. _fromからtoへ向かう容量capacityの辺をグラフに追加する
        2. toから_fromへ向かう容量0の辺をグラフに追加する
        """
        forward = [to, capacity, None]
        forward[2] = backward = [_from, 0, forward]
        self.graph[_from].append(forward)
        self.graph[to].append(backward)
 
    def bfs(self, s: int, t: int):
        """capacityが正の辺のみを通ってsからtに移動可能かどうかBFSで探索
        level: sからの最短路の長さ
        """
        self.level = [-1] * self.n
        q = deque([s])
        self.level[s] = 0
        while q:
            _from = q.popleft()
            for to, capacity, _ in self.graph[_from]:
                if capacity > 0 and self.level[to] < 0:
                    self.level[to] = self.level[_from] + 1
                    q.append(to)
 
    def dfs(self, _from: int, t: int, f: int) -> int:
        """流量が増加するパスをDFSで探索
        BFSによって作られた最短路に従ってfを更新する
        """
        if _from == t:
            return f
        for edge in self.itr[_from]:
            to, capacity, reverse_edge = edge
            if capacity > 0 and self.level[_from] < self.level[to]:
                d = self.dfs(to, t, min(f, capacity))
                if d > 0:
                    edge[1] -= d
                    reverse_edge[1] += d
                    return d
        return 0
 
    def max_flow(self, s: int, t: int):
        """s-tパス上の最大流を求める
        計算量: O(|E||V|^2)
        """
        flow = 0
        while True:
            self.bfs(s, t)
            if self.level[t] < 0:
                break
            self.itr = list(map(iter, self.graph))
            f = self.dfs(s, t, self.INF)
            while f > 0:
                flow += f
                f = self.dfs(s, t, self.INF)
        return flow

n = int(input())
a = list(map(int, input().split()))

dinic = Dinic(n + 2)
s = 0
t = n + 1
_sum = 0
for i in range(0, n):
    if a[i] > 0:
        dinic.add_edge(s, i+1, 0)
        dinic.add_edge(i+1, t, a[i])
        _sum += a[i]
    elif a[i] < 0:
        dinic.add_edge(s, i+1, -a[i])
        dinic.add_edge(i+1, t, 0)
    else:
        dinic.add_edge(s, i+1, 0)
        dinic.add_edge(i+1, t, 0)

for i in range(n):
    num = i+1
    next_num = 2 * num
    while next_num <= n:
        dinic.add_edge(num, next_num, 10**18)
        next_num += num

print(_sum - dinic.max_flow(s, t))

Solution (Python):
from collections import deque
 
 
class Dinic:
    def __init__(self, n: int):
        """頂点数をnとする"""
        self.INF = float("inf")
        self.n = n
        self.graph = [[] for _ in range(n)]
 
    def add_edge(self, _from: int, to: int, capacity: int):
        """残余グラフを構築
        1. _fromからtoへ向かう容量capacityの辺をグラフに追加する
        2. toから_fromへ向かう容量0の辺をグラフに追加する
        """
        forward = [to, capacity, None]
        forward[2] = backward = [_from, 0, forward]
        self.graph[_from].append(forward)
        self.graph[to].append(backward)
 
    def bfs(self, s: int, t: int):
        """capacityが正の辺のみを通ってsからtに移動可能かどうかBFSで探索
        level: sからの最短路の長さ
        """
        self.level = [-1] * self.n
        q = deque([s])
        self.level[s] = 0
        while q:
            _from = q.popleft()
            for to, capacity, _ in self.graph[_from]:
                if capacity > 0 and self.level[to] < 0:
                    self.level[to] = self.level[_from] + 1
                    q.append(to)
 
    def dfs(self, _from: int, t: int, f: int) -> int:
        """流量が増加するパスをDFSで探索
        BFSによって作られた最短路に従ってfを更新する
        """
        if _from == t:
            return f
        for edge in self.itr[_from]:
            to, capacity, reverse_edge = edge
            if capacity > 0 and self.level[_from] < self.level[to]:
                d = self.dfs(to, t, min(f, capacity))
                if d > 0:
                    edge[1] -= d
                    reverse_edge[1] += d
                    return d
        return 0
 
    def max_flow(self, s: int, t: int):
        """s-tパス上の最大流を求める
        計算量: O(|E||V|^2)
        """
        flow = 0
        while True:
            self.bfs(s, t)
            if self.level[t] < 0:
                break
            self.itr = list(map(iter, self.graph))
            f = self.dfs(s, t, self.INF)
            while f > 0:
                flow += f
                f = self.dfs(s, t, self.INF)
        return flow

n = int(input())
a = list(map(int, input().split()))

dinic = Dinic(n + 2)
s = 0
t = n + 1
_sum = 0
for i in range(0, n):
    if a[i] > 0:
        dinic.add_edge(s, i+1, 0)
        dinic.add_edge(i+1, t, a[i])
        _sum += a[i]
    elif a[i] < 0:
        dinic.add_edge(s, i+1, -a[i])
        dinic.add_edge(i+1, t, 0)
    else:
        dinic.add_edge(s, i+1, 0)
        dinic.add_edge(i+1, t, 0)

for i in range(n):
    num = i+1
    next_num = 2 * num
    while next_num <= n:
        dinic.add_edge(num, next_num, 10**18)
        next_num += num

print(_sum - dinic.max_flow(s, t))

Solution (Python):
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import dijkstra
import numpy as np

"""
最小カット
"""

N = int(input())
start = 0
goal = N+1

A = [0] + [int(x) for x in input().split()]

INF = 10 ** 12
graph = np.zeros((N+2,N+2),dtype=np.int64)
for i,a in enumerate(A[1:],1):
    if a >= 0:
        graph[start,i] = a
    else:
        graph[i,goal] = -a
for i in range(1,N+1):
    for j in range(2*i,N+1,i):
        if A[i] < 0 and A[j] > 0:
            graph[j][i] = INF

def max_flow(graph):
    flow = 0
    while True:
        dist,pred = dijkstra(graph, indices = start, return_predecessors = True, unweighted = True)
        if dist[goal] == np.inf:
            return flow
        path = []
        v = goal
        while True:
            path.append((pred[v],v))
            v = pred[v]
            if v == start:
                break
        add_flow = min(graph[x][y] for x,y in path)
        for x,y in path:
            graph[x][y] -= add_flow
            graph[y][x] += add_flow
        flow += add_flow

answer = sum(x for x in A if x > 0) - max_flow(graph)
print(answer)

Solution (Python):
import collections


class MaxFlow:
    """Dinic Algorithm: find max-flow
       complexity: O(EV^2)
       used in GRL6A(AOJ)
    """
    class Edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, V):
        """ V: the number of vertexes
            E: adjacency list
            source: start point
            sink: goal point
        """
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, fr, to, cap):
        self.E[fr].append(self.Edge(to, cap, len(self.E[to])))
        self.E[to].append(self.Edge(fr, 0, len(self.E[fr])-1))

    def dinic(self, source, sink, INF=10**9):
        """find max-flow"""
        maxflow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:
                return maxflow
            self.itr = [0] * self.V
            while True:
                flow = self.dfs(source, sink, INF)
                if flow > 0:
                    maxflow += flow
                else:
                    break

    def dfs(self, vertex, sink, flow):
        """find augmenting path"""
        if vertex == sink:
            return flow
        for i in range(self.itr[vertex], len(self.E[vertex])):
            self.itr[vertex] = i
            e = self.E[vertex][i]
            if e.cap > 0 and self.level[vertex] < self.level[e.to]:
                d = self.dfs(e.to, sink, min(flow, e.cap))
                if d > 0:
                    e.cap -= d
                    self.E[e.to][e.rev].cap += d
                    return d
        return 0

    def bfs(self, start):
        """find shortest path from start"""
        que = collections.deque()
        self.level = [-1] * self.V
        que.append(start)
        self.level[start] = 0

        while que:
            fr = que.popleft()
            for e in self.E[fr]:
                if e.cap > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[fr] + 1
                    que.append(e.to)


def main():
    INF = 10 ** 9
    N = int(input())
    A = [int(x) for x in input().split()]
    flow = MaxFlow(N + 2)
    source, sink = N, N + 1
    for i, a in enumerate(A):
        if a >= 0:
            flow.add_edge(source, i, a)
        else:
            flow.add_edge(i, sink, abs(a))
    for i in range(1, N + 1):
        for j in range(i, N + 1):
            if j % i == 0:
                flow.add_edge(j - 1, i - 1, INF)
    cost = flow.dinic(source, sink, INF)
    print(sum(a for a in A if a > 0) - cost)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque

class Dinic:
    def __init__(self,n,edges):
        self.n=n
        self.edges=[[] for _ in range(n)]
        self.iter=[0]*n
        self.level=None
        self.graph(edges)
    def graph(self,E):
        edges=self.edges
        for fr,to,cap in E:
            edges[fr].append([to,cap,len(edges[to])])
            edges[to].append([fr,0,len(edges[fr])-1])
    def maxflow(self,source,sink):
        max_flow=0
        while True:
            self.bfs(source)
            if self.level[sink]<0:
                return max_flow
            self.iter=[0]*self.n
            flow=self.dfs(source,sink,float('inf'))
            while flow:
                max_flow+=flow
                flow=self.dfs(source,sink,float('inf'))
    def bfs(self,source):
        edges=self.edges
        level=[-1]*self.n
        level[source]=0
        q=deque([source])
        while q:
            fr=q.popleft()
            for to,cap,_ in edges[fr]:
                if cap>0>level[to]:
                    level[to]=level[fr]+1
                    q.append(to)
        self.level=level
    def dfs(self,source,sink,flow):
        if source==sink:
            return flow
        while self.iter[source]<len(self.edges[source]):
            to,cap,rev=self.edges[source][self.iter[source]]
            if cap>0 and self.level[source]<self.level[to]:
                f=self.dfs(to,sink,min(flow,cap))
                if f:
                    self.edges[source][self.iter[source]][1]-=f
                    self.edges[to][rev][1]+=f
                    return f
            self.iter[source]+=1
        return 0

n=int(input())
A=list(map(int,input().split()))
Edges=[]
s=0
for i in range(n):
    if A[i]<=0:
        Edges.append((0,i+1,-A[i]))
    else:
        s+=A[i]
        Edges.append((i+1,n+1,A[i]))
    for j in range(2*(i+1),n+1,i+1):
        Edges.append((i+1,j,float('inf')))
dinic=Dinic(n+2,Edges)
print(s-dinic.maxflow(0,n+1))

Solution (Python):
from collections import deque

N = int(input())
A = list(map(int,input().split()))

P = N+2
es = [[] for i in range(P)] 

def add_edge(fr,to,cap):
    es[fr].append([to,cap,len(es[to])])
    es[to].append([fr,0,len(es[fr])-1])

INF = float('inf')
score = 0
for i,a in enumerate(A):
    if a < 0:
        add_edge(0,i+1,-a)
    elif a > 0:
        add_edge(i+1,N+1,a)
        score += a
for n in range(1,N//2+1):
    for m in range(2*n,N+1,n):
        add_edge(n,m,INF)

level = [0] * P
iters = [0] * P

def dinic_max_flow(s,t):
    global iters

    def _bfs(s):
        global level
        level = [-1] * P
        level[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for to,cap,rev in es[v]:
                if cap > 0 and level[to] < 0:
                    level[to] = level[v] + 1
                    q.append(to)

    def _dfs(v,t,f):
        if v == t: return f
        for i in range(iters[v],len(es[v])):
            iters[v] += 1
            to,cap,rev = es[v][i]
            if es[v][i][1] > 0 and level[v] < level[to]:
                d = _dfs(to,t,min(f,es[v][i][1]))
                if d > 0:
                    es[v][i][1] -= d 
                    es[to][rev][1] += d
                    return d
        return 0

    flow = 0
    while True:
        _bfs(s)
        if level[t] < 0: return flow
        iters = [0] * P
        f = 0
        while True:
            f = _dfs(s,t,INF)
            if f <= 0: break
            flow += f

print(score - dinic_max_flow(0,N+1))

Solution (Python):
from collections import deque

N = int(input())
A = list(map(int,input().split()))

P = N+2
es = [[] for i in range(P)] 

def add_edge(fr,to,cap):
    es[fr].append([to,cap,len(es[to])])
    es[to].append([fr,0,len(es[fr])-1])

INF = float('inf')
score = 0
for i,a in enumerate(A):
    if a > 0:
        add_edge(0,i+1,a)
        score += a
    elif a < 0:
        add_edge(i+1,N+1,-a)
for n in range(1,N//2+1):
    for m in range(2*n,N+1,n):
        add_edge(m,n,INF)

level = [0] * P
iters = [0] * P

def dinic_max_flow(s,t):
    global iters

    def _bfs(s):
        global level
        level = [-1] * P
        level[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for to,cap,rev in es[v]:
                if cap > 0 and level[to] < 0:
                    level[to] = level[v] + 1
                    q.append(to)

    def _dfs(v,t,f):
        if v == t: return f
        for i in range(iters[v],len(es[v])):
            iters[v] += 1
            to,cap,rev = es[v][i]
            if es[v][i][1] > 0 and level[v] < level[to]:
                d = _dfs(to,t,min(f,es[v][i][1]))
                if d > 0:
                    es[v][i][1] -= d 
                    es[to][rev][1] += d
                    return d
        return 0

    flow = 0
    while True:
        _bfs(s)
        if level[t] < 0: return flow
        iters = [0] * P
        f = 0
        while True:
            f = _dfs(s,t,INF)
            if f <= 0: break
            flow += f

print(score - dinic_max_flow(0,N+1))

Solution (Python):


import math

def gcd(a, b):
    if a < b:
        a, b = b, a
    q, r = a, b
    while r:
        q, r = r, q % r

    return q


def lcm(a, b):
    return a * b // gcd(a, b)

MAX_N = 102
INF = 10 ** 12
SRC = 0
DST = MAX_N - 1
g = [[0] * MAX_N for _ in range(MAX_N)]
level = []
visited = []
n = 0


def bfs(s):
    global level

    level = [-1] * MAX_N
    level[s] = 0
    que = [s]
    while 0 < len(que):
        v = que.pop(0)
        for w in range(MAX_N):
            if 0 < g[v][w] and level[w] < 0:
                level[w] = level[v] + 1
                que.append(w)


def dfs(v, t, f):
    global g, visited

    if v == t:
        return f
    for w in range(visited[v], MAX_N):
        visited[v] = w
        if 0 < g[v][w] and level[v] < level[w]:
            d = dfs(w, t, min(f, g[v][w]))
            if 0 < d:
                g[v][w] -= d
                g[w][v] += d
                return d

    return 0


def max_flow():
    global visited

    flow = 0
    while True:
        bfs(SRC)
        if level[DST] < 0:
            return flow
        visited = [0] * MAX_N
        f = dfs(SRC, DST, INF)
        while 0 < f:
            flow += f
            f = dfs(SRC, DST, INF)


def solve(n, a):
    global g

    sum_positive = sum([v for v in a if 0 < v])

    for i in range(1, n + 1):
        if 0 < a[i]:
            g[SRC][i] = a[i]
        elif a[i] < 0:
            g[i][DST] = -a[i]
            for j in range(i * 2, n + 1, i):
                if 0 < a[j]:
                    g[j][i] = INF

    return sum_positive - max_flow()


def main():
    global n

    n = int(input())
    a = list(map(int, input().split()))
    a = [0] + a

    print(solve(n, a))


if __name__ == '__main__':
    main()

Solution (Python):


import copy
import queue

N = int(input())
a_list = list(map(int, input().split()))

gain = sum([a for a in a_list if a > 0])


S = 0
T = N + 1
c = [{} for i in range(N + 2)]
for i, a in enumerate(a_list):
    index = i + 1
    if a <= 0:
        c[S][index] = -a
    else:
        c[index][T] = a
    for j in range(index, N + 1, index):
        if not j == index:
            c[index][j] = 10e15


r = copy.deepcopy(c)


max_flow = 0
while True:
    
    q, s, p = queue.Queue(), {S}, None
    q.put((S,))
    findPath = False
    while not q.empty() and not findPath:
        cand_path = q.get(False)
        for to, path in r[cand_path[-1]].items():
            if path == 0:
                continue
            elif to == T:
                p = cand_path + (to,)
                findPath = True
            elif not to in s:
                q.put(cand_path + (to,))
                s.add(to)

    if not findPath:
        break

    
    min_flow = min([r[p[i]][p[i+1]] for i in range(len(p)-1)])
    max_flow += min_flow
    for i in range(len(p)-1):
        r[p[i]][p[i+1]] -= min_flow
        if p[i] in r[p[i+1]]:
            r[p[i+1]][p[i]] += min_flow
        else:
            r[p[i+1]][p[i]] = min_flow

print(gain - max_flow)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(200000)
n = int(input())
houseki = list(map(int,input().split()))
g = [[] for i in range(n+2)]
INF = float("inf")
MAX = 0
for i in range(n):
  if houseki[i] <= 0:
    g[0].append([i+1,-houseki[i],len(g[i+1])])
    g[i+1].append([0,0,len(g[0])-1])
  else:
    g[n+1].append([i+1,0,len(g[i+1])])
    g[i+1].append([n+1,houseki[i],len(g[n+1])-1])
    MAX += houseki[i]
  j = (i+1)*2
  while j <= n:
    g[i+1].append([j,INF,len(g[j])])
    g[j].append([i+1,0,len(g[i+1])-1])
    j += i+1
def bfs(s,t):
  global level
  que = deque([s])
  level[s] = 0
  while que:
    v = que.popleft()
    lv = level[v] +1
    for y, cap, rev in g[v]:
      if cap and level[y] is None:
        level[y] = lv
        que.append(y)
  return level[t] if level[t] else 0
def dfs(x,t,f):
  if x == t:
    return f
  for j in range(it[x],len(g[x])):
    it[x] = j
    y, cap, rev = g[x][j]
    if cap and level[x] < level[y]:
      d = dfs(y,t,min(f,cap))
      if d:
        g[x][j][1] -= d
        g[y][rev][1] += d
        return d
  return 0
 
flow = 0
f = INF = float("inf")
level = [None]*(n+2)
while bfs(0,n+1):
  it = [0]* (n+2)
  f = INF
  while f:
    f = dfs(0,n+1,INF)
    flow += f
  level = [None]*(n+2)
print(MAX-flow)

Solution (Python):
import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        self.inf = float('inf')
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf

def inpl(): return [int(i) for i in input().split()]
N = int(input())
a = inpl()
K = Dinic(N+2)
inf = float('inf')
for i, v in enumerate(a,1):
    if v > 0:
        K.addedge(i, N+1, v)
    else:
        K.addedge(0, i, -v)
for i in range(1,N+1):
    for j in range(2*i, N+1, i):
        K.addedge(i, j, inf)

print(sum([i for i in a if i > 0]) - K.getmf(0, N+1))

Solution (Python):
class FK:
    def __init__(self,n):
        self.table=[[0]*n for i in range(n)]
        self.n=n
    
    def add(self,x,y,f):
        self.table[x][y]=f
        
    def ford(self,s,t,f):
        self.visit[s]=True
        if s==t:
            return f
        for i in range(self.n):
            if (not self.visit[i]) and self.table[s][i]>0:
                df=self.ford(i,t,min(f,self.table[s][i]))
                if df>0:
                    self.table[s][i]-=df
                    self.table[i][s]+=df
                    return df
        return 0
    
    def flow(self,s,t):
        ans=0
        inf=10**20
        while True:
            self.visit=[False]*(self.n)
            df=self.ford(s,t,inf)
            if df==0:
                break
            ans+=df
        return ans

N=int(input())
P=[int(i) for i in input().split()]
inf=10**20
maxflow=FK(N+2)
for i in range(1,N+1):
    if P[i-1]>0:
        maxflow.add(i,N+1,P[i-1])
    else:
        maxflow.add(0,i,-P[i-1])
    for j in range(2*i,N+1,i):
        maxflow.add(i,j,inf)
ans=maxflow.flow(0,N+1)
num=sum([p for p in P if p>0])
print(num-ans)

Solution (Python):
from collections import deque
class Dinic:
    def __init__(self,number):
        self.table = [[0]*(number) for i in range(number)]
        self.n=number
    
    def add(self,x,y,f):
        self.table[x][y]=f
    
    def bfs(self,x):
        self.visit[x]=0
        h=deque()
        h.append(x)
        while h:
            y=h.popleft()
            for i in range(self.n):
                if self.visit[i]==-1 and self.table[y][i]>0:
                    self.visit[i]=self.visit[y]+1
                    h.append(i)
        return 0
    
    def dinic(self,s,t,f):
        if s==t:
            return f
        for i in range(self.n):
            if self.visit[i]>self.visit[s] and self.table[s][i]>0:
                df = self.dinic(i,t,min(f,self.table[s][i]))
                if df>0:
                    self.table[s][i]-=df
                    self.table[i][s]+=df
                    return df
        return 0
    
    def flow(self,s,t):
        ans=0
        inf=10**20
        while True:
            self.visit=[-1]*(self.n)
            self.bfs(s)
            if self.visit[t]==-1:
                break
            while True:
                df=self.dinic(s,t,inf)
                if df==0:
                    break
                ans+=df
        return ans
N=int(input())
P=[int(i) for i in input().split()]
inf=10**20
maxflow=Dinic(N+2)
for i in range(1,N+1):
    if P[i-1]>0:
        maxflow.add(i,N+1,P[i-1])
    else:
        maxflow.add(0,i,-P[i-1])
    for j in range(2*i,N+1,i):
        maxflow.add(i,j,inf)
ans=maxflow.flow(0,N+1)
num=sum([p for p in P if p>0])
print(num-ans)

Solution (Python):
from  collections import deque
N=int(input())
P=[int(i) for i in input().split()]
inf = 10**20
table=[[0]*(N+2) for i in range(N+2)]
for i in range(1,N+1):
    if P[i-1]>0:
        table[i][N+1]=P[i-1]
    else:
        table[0][i]=-P[i-1]
    for j in range(2*i,N+1,i):
        table[i][j]=inf
        
def bfs(x):
    visit[x]=0
    h=deque()
    h.append(x)
    while h:
        y=h.popleft()
        for i in range(N+2):
            if visit[i]==-1 and table[y][i]>0:
                visit[i]=visit[y]+1
                h.append(i)
    return 0

def dinic(s,t,f):
    if s==t:
        return f
    for i in range(N+2):
        if visit[i]>visit[s] and table[s][i]>0:
            df = dinic(i,t,min(f,table[s][i]))
            if df>0:
                table[s][i]-=df
                table[i][s]+=df
                return df
    return 0

ans=0
while True:
    visit=[-1]*(N+2)
    bfs(0)
    
    if visit[N+1]==-1:
        break
    while True:
        df=dinic(0,N+1,inf)
        if df==0:
            break
        ans+=df
        
num=sum([p for p in P if p>0])
print(num-ans)

Solution (Python):
N=int(input())
P=[int(i) for i in input().split()]
inf = 10**20
table=[[0]*(N+2) for i in range(N+2)]
for i in range(1,N+1):
    if P[i-1]>0:
        table[i][N+1]=P[i-1]
    else:
        table[0][i]=-P[i-1]
    for j in range(2*i,N+1,i):
        table[i][j]=inf

def fk(x,t,f):
    
    visit[x]=True
    if x==t:
        return f
    for i in range(N+2):
        if (not visit[i]) and table[x][i]>0:
            df=fk(i,t,min(f,table[x][i]))
            if df>0:
                table[x][i]-=df
                table[i][x]+=df
                return df
    return 0

ans=0
while True:
    visit=[False]*(N+2)
    df=fk(0,N+1,inf)
    if df>0:
        ans+=df
    else:
        break
num=sum([p for p in P if p>0])
print(num-ans)

Solution (Python):
N=int(input())
P=[int(i) for i in input().split()]
inf = 10**20
table=[[0]*(N+2) for i in range(N+2)]
for i in range(1,N+1):
    if P[i-1]>0:
        table[i][N+1]=P[i-1]
    else:
        table[0][i]=-P[i-1]
    for j in range(2*i,N+1,i):
        table[i][j]=inf

def fk(x,t,f):
    
    visit[x]=True
    if x==t:
        return f
    for i in range(N+2):
        if (not visit[i]) and table[x][i]>0:
            df=fk(i,t,min(f,table[x][i]))
            if df>0:
                table[x][i]-=df
                table[i][x]+=df
                return df
    return 0

ans=0
while True:
    visit=[False]*(N+2)
    df=fk(0,N+1,inf)
    if df>0:
        ans+=df
    else:
        break
num=sum([p for p in P if p>0])
print(num-ans)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

INF = 1 << 60

def main():
  N = read()
  A = reads()
  offset = sum(a for a in A if a > 0)
  di = dinic(N+2) 
  for i in range(1, N+1):
    a = A[i-1]
    if a <= 0:
      di.add_edge(0, i, -a)
    else:
      di.add_edge(i, N+1, a)
    for j in range(2*i, N+1, i):
      di.add_edge(i, j, INF)
  ans = offset - di.max_flow(0, N+1)
  print(ans)

class dinic:
  def __init__(self, N): self.size = N; self.edges = [[] for _ in range(N)]
  def add_edge(self, u, v, c): self.edges[u].append((v, c)); self.edges[v].append((u, 0))
  def bfs(self, cap, s):
    N = self.size; edges = self.edges
    level = [-1] * N; level[s] = 0
    que = deque([s])
    while len(que) > 0:
      u = que.popleft()
      for v, _ in edges[u]:
        if cap[u][v] > 0 and level[v] < 0: level[v] = level[u] + 1; que.append(v)
    return level
  def dfs(self, cap, itr, level, u, t, f):
    N = self.size; edges = self.edges
    if u == t: return f
    for i in range(itr[u], len(edges[u])):
      itr[u] = i
      v, _ = edges[u][i]
      if cap[u][v] > 0 and level[u] < level[v]:
        d = self.dfs(cap, itr, level, v, t, min(f, cap[u][v]))
        if d > 0: cap[u][v] -= d; cap[v][u] += d; return d
    return 0
  def max_flow(self, s, t):
    N = self.size; edges = self.edges; cap = [[0] * N for _ in range(N)]
    for u in range(N):
      for v, c in edges[u]: cap[u][v] += c
    flow = 0
    while True:
      level = self.bfs(cap, s)
      if level[t] < 0: return flow
      itr = [0] * N
      while True:
        f = self.dfs(cap, itr, level, s, t, INF)
        if f <= 0: break
        flow += f

main()

Solution (Python):
from collections import deque


def addEdge(adjL, vFr, vTo, cap):
    adjL[vFr].append([vTo, cap, len(adjL[vTo])])
    adjL[vTo].append([vFr, 0, len(adjL[vFr]) - 1]) 



def Dinic(adjL, vSt, vEn):

    
    def BFS(vSt):
        dist[vSt] = 0
        Q = deque([vSt])
        while Q:
            vNow = Q.popleft()

            for i, (v2, cap, iRev) in enumerate(adjL[vNow]):
                if dist[v2] == -1 and cap > 0:
                    
                    dist[v2] = dist[vNow] + 1
                    Q.append(v2)


    
    def DFS(vNow, vEn, fNow):
        if vNow == vEn:
            
            return fNow

        
        iSt = iNext[vNow]
        for i, (v2, cap, iRev) in enumerate(adjL[vNow][iSt:], iSt):
            if dist[vNow] < dist[v2] and cap > 0:
                
                df = DFS(v2, vEn, min(fNow, cap))
                if df > 0:
                    
                    adjL[vNow][i][1] -= df
                    adjL[v2][iRev][1] += df
                    return df

            iNext[vNow] += 1

        
        return 0


    numV = len(adjL)
    MaximumFlow = 0
    while True:
        
        dist = [-1] * numV
        BFS(vSt)
        if dist[vEn] == -1:
            
            return MaximumFlow

        iNext = [0] * numV
        while True:
            
            df = DFS(vSt, vEn, float('inf'))

            if df == 0:
                
                break

            
            MaximumFlow += df


N = int(input())
As = list(map(int, input().split()))

adjList = [[] for v in range(N + 2)]
for i, A in enumerate(As, 1):
    if A <= 0:
        addEdge(adjList, 0, i, -A)
    else:
        addEdge(adjList, i, N + 1, A)

for i in range(1, N + 1):
    for j in range(2 * i, N + 1, i):
        addEdge(adjList, i, j, float('inf'))


mf = Dinic(adjList, 0, N + 1)
print(sum([A for A in As if A > 0]) - mf)