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



Sample input:
6
1 2 -6 4 5 3


Sample output:
12

Submission status: Accepted

Solution code:
def edmonds_karp(s, t, C):
    '''
    s, t: start, target (integer)
    C: Array of dict ([from][to] -> length)
    ret: maximum_flow (integer)
    '''
    import copy
    import collections

    r = copy.deepcopy(c)  # Residual network
    maxf = 0

    while True:
        q, found = collections.deque(), False
        q.append(([s], 10 ** 15))
        while len(q) > 0 and not found:
            p, minf = q.popleft()
            for to, flow in r[p[-1]].items():
                if flow == 0:
                    continue
                elif to == t:
                    p, minf = p + [to], min(flow, minf)
                    found = True
                    break
                elif not to in p:
                    q.append((p + [to], min(flow, minf)))

        if not found:
            break

        for i in range(len(p) - 1):
            r[p[i]][p[i + 1]] -= minf
            if p[i] in r[p[i + 1]]:
                r[p[i + 1]][p[i]] += minf
            else:
                r[p[i + 1]][p[i]] = minf
        maxf += minf

    return maxf


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

gain = sum([max(a, 0) for a in A])

# Flow network
S, T = 0, N + 1
c = [{} for i in range(N + 2)]
for i in range(N):
    ix = i + 1
    if A[i] <= 0:
        c[S][ix] = -A[i]
    else:
        c[ix][T] = A[i]

    for j in range(2 * ix, N + 1, ix):
        c[ix][j] = 10 ** 15

print(gain - edmonds_karp(S, T, c))

Submission status: Accepted

Solution code:
import copy
import collections

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

gain = sum([max(a, 0) for a in A])

# Flow network
S, T = 0, N + 1
c = [{} for i in range(N + 2)]
for i in range(N):
    ix = i + 1
    if A[i] <= 0:
        c[S][ix] = -A[i]
    else:
        c[ix][T] = A[i]

    for j in range(2 * ix, N + 1, ix):
        c[ix][j] = 10e15

# Residual network
r = copy.deepcopy(c)

# Edmonds-Karp algorithm
max_flow = 0
while True:
    # Find path to T
    q, s, p = collections.deque(), {S}, None
    q.append((S,))
    findPath = False
    while not len(q) == 0 and not findPath:
        cand_path = q.popleft()
        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.append(cand_path + (to,))
                s.add(to)

    if not findPath:
        break

    # Minimum flow
    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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
from collections import deque

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

P = N+2
es = [[] for i in range(P)] # [[to1,cap1,rev1], ...]

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 #cap
                    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))

Submission status: Accepted

Solution code:
from collections import deque

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

P = N+2
es = [[] for i in range(P)] # [[to1,cap1,rev1], ...]

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 #cap
                    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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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])

# Flow network
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

# Residual network
r = copy.deepcopy(c)

# Edmonds-Karp algorithm
max_flow = 0
while True:
    # Find path to T
    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

    # Minimum flow
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)
    #print(table,visit)
    if visit[N+1]==-1:
        break
    while True:
        df=dinic(0,N+1,inf)
        if df==0:
            break
        ans+=df
        #print(ans)
num=sum([p for p in P if p>0])
print(num-ans)

Submission status: Accepted

Solution code:
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
#print(table)
def fk(x,t,f):
    #print(x)
    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)

Submission status: Accepted

Solution code:
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) # 0: source, N+1: target
  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()

Submission status: Accepted

Solution code:
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]) # 逆辺


# Dinic法（最大フローを求める）
def Dinic(adjL, vSt, vEn):

    # 始点からの最短距離を、BFSで求める
    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)


    # 残余グラフの始点から終点までの経路（増加パス）を、DFSで探索する
    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:
        # 始点からの最短距離を、BFSで求める
        dist = [-1] * numV
        BFS(vSt)
        if dist[vEn] == -1:
            # 終点までの経路が見つからない場合、最大フローの値を返す
            return MaximumFlow

        iNext = [0] * numV
        while True:
            # 残余グラフの始点から終点までの経路（増加パス）を、DFSで探索する
            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'))

# Dinic法（最大フローを求める）
mf = Dinic(adjList, 0, N + 1)
print(sum([A for A in As if A > 0]) - mf)