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:
from collections import deque


class Dinic:
    def __init__(self, v, inf=10**9 + 7):
        self.V = v
        self.inf = inf
        self.G = [list() for _ in range(v)]
        self.level = [-1 for _ in range(v)]
        self.iter = [0] * v

    def addedge(self, fr, to, cap):
        """
        G[fr] = [to, cap, rev]
        """
        go = [to, cap, None]
        go[2] = back = [fr, 0, go]
        self.G[fr].append(go)
        self.G[to].append(back)

    def bfs(self, st, en):
        q = deque([st])
        self.level = [-1 for _ in range(self.V)]
        self.level[st] = 0
        while q:
            cur = q.popleft()
            for x, cap, _ in self.G[cur]:
                if cap and self.level[x] < 0:
                    self.level[x] = self.level[cur] + 1
                    q.append(x)
        return self.level[en] > 0

    def dfs(self, v, t, f):
        if v == t:
            return f
        for e in self.iter[v]:
            w, cap, rev = e
            if cap and self.level[v] < self.level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.iter = list(map(iter, self.G))
            f = self.dfs(s, t, self.inf)
            while f:
                flow += f
                f = self.dfs(s, t, self.inf)
        return flow

def main():
    n = int(input())
    a = list(map(int, input().split()))
    D = Dinic(n+2)
    ret = 0
    for i,e in enumerate(a, 1):
      if e > 0:
        ret += e
        D.addedge(i, n+1, e)
      else:
        D.addedge(0, i, -e)
    for i in range(1, n//2 + 1):
      for j in range(i*2, n+1, i):
        D.addedge(i, j, 10**12)
    loss = D.flow(0, n+1)
    return ret - loss

print(main())

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
a = list(map(int, input().split()))


class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


graph = Dinic(n + 2)
for i in range(n):
    if a[i] >= 0:
        graph.add_edge(i, n, a[i])
        continue
    graph.add_edge(n + 1, i, -a[i])
for i in range(1, n + 1):
    for j in range(2 * i, n + 1, i):
        graph.add_edge(i-1, j-1, 10**11)
print(sum([max(0, i) for i in a])-graph.flow(n+1, n))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class Dinic:
    """ 最大流(Dinic) """

    INF = 10 ** 18

    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None
 
    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])
 
    def bfs(self, s):
        from collections import deque

        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, _ in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth
 
    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0
 
    def max_flow(self, s, t):
        INF = Dinic.INF
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, INF)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, INF)

N = INT()
A = LIST()

# 最大流を最小カットに使用、流量がコストとみなせる
dinic = Dinic(N+2)
s = N
t = N + 1
total = 0
for i, a in enumerate(A):
    if a < 0:
        # 元々損失の部分はそのままコストとして扱う
        dinic.add_link(s, i, -a)
    elif a > 0:
        # 利益については、予め利益を得られるとして、得られなくなる方の選択肢にコストとして足す
        dinic.add_link(i, t, a)
        total += a

for i in range(1, N+1):
    j = i
    while j <= N:
        # 制約で異なる選択肢を選べない組にコストINFの辺を張る
        dinic.add_link(i-1, j-1, INF)
        j += i

res = dinic.max_flow(s, t)
# 最大利益 = 調整分 - 最小カット
print(total - res)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    # Dinic's algorithm
    from collections import deque
    class Dinic:
        def __init__(self, N):
            self.N = N
            self.G = [[] for i in range(N)]

        def add_edge(self, fr, to, cap):
            forward = [to, cap, None]
            forward[2] = backward = [fr, 0, forward]
            self.G[fr].append(forward)
            self.G[to].append(backward)

        def add_multi_edge(self, v1, v2, cap1, cap2):
            edge1 = [v2, cap1, None]
            edge1[2] = edge2 = [v1, cap2, edge1]
            self.G[v1].append(edge1)
            self.G[v2].append(edge2)

        def bfs(self, s, t):
            self.level = level = [None] * self.N
            deq = deque([s])
            level[s] = 0
            G = self.G
            while deq:
                v = deq.popleft()
                lv = level[v] + 1
                for w, cap, _ in G[v]:
                    if cap and level[w] is None:
                        level[w] = lv
                        deq.append(w)
            return level[t] is not None

        def dfs(self, v, t, f):
            if v == t:
                return f
            level = self.level
            for e in self.it[v]:
                w, cap, rev = e
                if cap and level[v] < level[w]:
                    d = self.dfs(w, t, min(f, cap))
                    if d:
                        e[1] -= d
                        rev[1] += d
                        return d
            return 0

        def flow(self, s, t):
            flow = 0
            INF = 10 ** 9 + 7
            G = self.G
            while self.bfs(s, t):
                *self.it, = map(iter, self.G)
                f = INF
                while f:
                    f = self.dfs(s, t, INF)
                    flow += f
            return flow

    inf = 1<<40
    N = int(input())
    A = list(map(int, input().split()))
    dinic = Dinic(N+2)
    ans = 0
    for i, a in enumerate(A):
        if a > 0:
            ans += a
            #dinic.add_edge(0, i+1, 0)
            dinic.add_edge(i+1, N+1, a)
        else:
            dinic.add_edge(0, i+1, -a)
            #dinic.add_edge(i+1, N+1, 0)
    for i in range(1, N+1):
        for k in range(1, N+1):
            if i*k > N:
                break
            dinic.add_edge(i, i*k, inf)

    print(ans - dinic.flow(0, N+1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy
N = int(input())
a0 = list(map(int, input().split()))

for i in range(N, 0, -1):
    if a0[i - 1] < 0:
        tmp = 0
        b = []
        for j in range(1, 101):
            if i * j - 1 >= N:
                break
            tmp += a0[i * j - 1]
            b.append(i * j - 1)
        if tmp < 0:
            for j in b:
                a0[j] = 0

for k1 in range(N, 0, -1):
    for k2 in range(k1-1, 0, -1):
        a = deepcopy(a0)
        for j in range(1, 101):
            if k1*j-1 >= N:
                break
            a[k1*j-1] = 0
        for j in range(1, 101):
            if k2*j-1 >= N:
                break
            a[k2*j-1] = 0
        for i in range(N, 0, -1):
            if a[i - 1] < 0:
                tmp = 0
                b = []
                for j in range(1, 101):
                    if i * j - 1 >= N:
                        break
                    tmp += a[i * j - 1]
                    b.append(i * j - 1)
                if tmp < 0:
                    for j in b:
                        a[j] = 0

        for i in range(N, 0, -1):
            if a0[i - 1] < 0:
                tmp = 0
                b = []
                for j in range(1, 101):
                    if i * j - 1 >= N:
                        break
                    tmp += a0[i * j - 1]
                    b.append(i * j - 1)
                if tmp < 0:
                    for j in b:
                        a0[j] = 0

        if sum(a) > sum(a0):
            a0 = a

print(sum(a0))

Submission status: Accepted

Solution code:
from collections import deque
class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]#(行き先、容量、逆辺の参照)
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow
N = int(input())
a = list(map(int, input().split()))
D = Dinic(N+2)
inf = 10**18
profit = 0
cost = 0
for i in range(N):
    if a[i]>=0:
        D.add_edge(i, N+1, a[i])
    else:
        D.add_edge(N, i, -a[i])
        cost+=a[i]
    profit+=abs(a[i])
    

for i in range(1, N+1):
    for k in range(2, N//i+1):
        D.add_edge(i-1, i*k-1, inf)
f = D.flow(N, N+1)
print(profit-f+cost)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,*A = map(int,read().split())

class Dinic:
    def __init__(self, N, source, sink):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.source = source
        self.sink = sink

    def add_edge(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, 0, n1]) # 逆辺を cap 0 で追加
        
    def add_edge_undirected(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, cap, n1])
        
    def bfs(self):
        level = [0] * self.N
        G = self.G; source = self.source; sink = self.sink
        q = deque([source])
        level[source] = 1
        pop = q.popleft; append = q.append
        while q:
            v = pop()
            lv = level[v] + 1
            for to, cap, rev in G[v]:
                if not cap:
                    continue
                if level[to]:
                    continue
                level[to] = lv
                if to == sink:
                    self.level = level
                    return
                append(to)
        self.level = level
        
    def dfs(self,v,f):
        if v == self.sink:
            return f
        G = self.G
        prog = self.progress
        level = self.level
        lv = level[v]
        E = G[v]
        for i in range(prog[v],len(E)):
            to, cap, rev = E[i]
            prog[v] = i
            if not cap:
                continue
            if level[to] <= lv:
                continue
            x = f if f < cap else cap
            ff = self.dfs(to, x)
            if ff:
                E[i][1] -= ff
                G[to][rev][1] += ff
                return ff
        return 0
    
    def max_flow(self):
        INF = 10**18
        flow = 0
        while True:
            self.bfs()
            if not self.level[self.sink]:
                return flow
            self.progress = [0] * self.N
            while True:
                f = self.dfs(self.source, INF)
                if not f:
                    break
                flow += f
        return flow

source = 0; sink = N+1; INF = 10 ** 18
dinic = Dinic(N+2,source,sink)
add = dinic.add_edge

for i,x in enumerate(A,1):
    if x < 0:
        # source側：割るものを表現。sink側にうつすときにカット-xが必要。
        add(source,i,-x)
    else:
        # sink側：割らないものを表現。source側にうつすときにカットxが必要。
        add(i,sink,x)

for i in range(1,N+1):
    for j in range(i+i,N+1,i):
        # iを割るならjも割る。iを割ってjを割らないのは禁止
        # iがsourceでjがsinkなのは禁止
        add(i,j,INF)

f = dinic.max_flow()
x = sum(x for x in A if x >= 0)
answer = x - f

print(answer)

Submission status: Accepted

Solution code:
from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))

class Dinic():
    def __init__(self, n, s, t):
        self.n, self.s, self.t = n, s, t
        self.to = defaultdict(list)
        self.level = [-1]
        self.max_flow = -1

    def add_edge(self, u, v, cap):
        u_index_in_to_v = len(self.to[v])
        v_index_in_to_u = len(self.to[u])
        self.to[u].append([v, cap, u_index_in_to_v])
        self.to[v].append([u, 0, v_index_in_to_u])

    def set_level(self):
        s = self.s
        level = [-1] * self.n
        level[s] = 0
        q = deque()
        q.append([s, 0])
        while q:
            u, u_level = q.popleft()
            for v, cap, _ in self.to[u]:
                if cap == 0: continue
                if level[v] != -1: continue
                level[v] = u_level + 1
                if v == self.t:
                    self.level=level
                    return True
                q.append([v, u_level + 1])
        return False

    def dfs(self, u=-1, flow_to_me=10 ** 16):
        if u == -1: u = self.s
        if u == self.t: return flow_to_me
        flow_from_me = 0
        u_level = self.level[u]
        for utov_i, (v, cap, vtou_i) in enumerate(self.to[u]):
            if self.level[v] != u_level + 1: continue
            if cap == 0: continue
            flow_to_v = self.dfs(v, min(cap, flow_to_me - flow_from_me))
            if not flow_to_v: continue
            flow_from_me += flow_to_v
            self.to[u][utov_i][1] -= flow_to_v
            self.to[v][vtou_i][1] += flow_to_v
        return flow_from_me

    def calculation(self):
        res = 0
        while self.set_level():
            res += self.dfs()
        return res

    # これが出力用
    def get_max_flow(self):
        if self.max_flow == -1:
            self.max_flow = self.calculation()
        return self.max_flow

def main():
    n = int(input())
    aa = LI()
    mf = Dinic(n + 2, 0, n + 1)
    max_sum = 0
    for i, a in enumerate(aa, 1):
        if a > 0:
            mf.add_edge(i, n + 1, a)
            max_sum += a
        else:
            mf.add_edge(0, i, -a)
    for i in range(1, n // 2 + 1):
        for j in range(i * 2, n + 1, i):
            mf.add_edge(i, j, 10 ** 12)
    print(max(0, max_sum - mf.get_max_flow()))

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import deque

MAX_V = 100000
G = [[] for _ in range(MAX_V)]
level = [0 for _ in range(MAX_V)]
iter = [0 for _ in range(MAX_V)]


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


# sからの最短距離をBFSで計算
def bfs(s):
    for i in range(MAX_V):
        level[i] = -1
    que = deque()
    level[s] = 0
    que.append(s)
    while len(que) != 0:
        v = que.popleft()
        for e in G[v]:
            if e[1] > 0 and level[e[0]] < 0:
                level[e[0]] = level[v] + 1
                que.append(e[0])


def dfs(v, t, f):
    if v == t:
        return f
    for i in range(iter[v], len(G[v])):
        if G[v][i][1] > 0 and level[v] < level[G[v][i][0]]:
            d = dfs(G[v][i][0], t, min(G[v][i][1], f))
            if d > 0:
                G[v][i] = (G[v][i][0], G[v][i][1]-d, G[v][i][2])
                G[G[v][i][0]][G[v][i][2]] = (G[G[v][i][0]][G[v][i][2]][0], G[G[v][i][0]][G[v][i][2]][1]+d, G[G[v][i][0]][G[v][i][2]][2])
                return d
    return 0


def max_flow(s, t, FLW_LIM=10**18):
    flow = 0
    while True:
        bfs(s)
        if level[t] < 0:
            return flow
        for i in range(MAX_V):
            iter[i] = 0
        f = 0
        while True:
            f = dfs(s, t, FLW_LIM)
            if f == 0:
                break
            flow += f


def main():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(1, n+1):
        for j in range(i, n+1, i):
            add_edge(i, j, 10**18+5)
    for i, _a in enumerate(a):
        if _a < 0:
            add_edge(0, i+1, -_a)
        else:
            add_edge(i+1, n+1, _a)
    ans = 0
    for _a in a:
        if _a > 0:
            ans += _a
    print(ans - max_flow(0, n+1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return

#B
def B():

    return

#C
def C():
    def bfs(s,g,n):
        bfs_map = [-1 for i in range(n)]
        bfs_map[s] = 0
        q = deque()
        q.append(s)
        fin = False
        while q:
            x = q.popleft()
            for y in range(n):
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    if y == g:
                        fin = True
                        break
                    q.append(y)
            if fin:
                break

        if bfs_map[g] == -1:
            return None,0
        path = [None]*(bfs_map[g]+1)
        m = float("inf")
        path[bfs_map[g]] = g
        y = g
        for i in range(bfs_map[g])[::-1]:
            for x in range(n):
                if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                    path[i] = x
                    if c[x][y] < m:
                        m = c[x][y]
                    y = x
                    break
        return path,m

    def ford_fulkerson(s,g,c,n):
        f = 0
        while 1:
            p,m = bfs(s,g,n)
            if not m:break
            f += m
            for i in range(len(p)-1):
                c[p[i]][p[i+1]] -= m
                c[p[i+1]][p[i]] += m
        return f

    n = I()
    a = LI()
    e = n+2
    ma = 10**9
    c = [[0]*e for i in range(e)]
    for i in range(n):
        d = i+1
        j = 2*d
        c[0][d] = ma
        c[d][n+1] = ma-a[i]
        while j <= n:
            c[j][d] = float("inf")
            j += d
    print(ma*n-ford_fulkerson(0,n+1,c,e))
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return

#B
def B():

    return

#C
def C():
    def bfs(s,g,n):
        bfs_map = [-1 for i in range(n)]
        bfs_map[s] = 0
        q = deque()
        q.append(s)
        fin = False
        while q:
            x = q.popleft()
            for y in v[x]:
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    if y == g:
                        fin = True
                        break
                    q.append(y)
            if fin:
                break

        if bfs_map[g] == -1:
            return None,0
        path = [None]*(bfs_map[g]+1)
        m = float("inf")
        path[bfs_map[g]] = g
        y = g
        for i in range(bfs_map[g])[::-1]:
            for x in v[y]:
                if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                    path[i] = x
                    if c[x][y] < m:
                        m = c[x][y]
                    y = x
                    break
        return path,m

    def ford_fulkerson(s,g,c,n):
        f = 0
        while 1:
            p,m = bfs(s,g,n)
            if not m:break
            f += m
            for i in range(len(p)-1):
                c[p[i]][p[i+1]] -= m
                c[p[i+1]][p[i]] += m
        return f

    n = I()
    a = LI()
    e = n+2
    ma = 10**9
    c = [[0]*e for i in range(e)]
    v = [[] for i in range(e)]
    for i in range(n):
        d = i+1
        j = 2*d
        c[0][d] = ma
        v[0].append(d)
        v[d].append(0)
        c[d][n+1] = ma-a[i]
        v[d].append(n+1)
        v[n+1].append(d)
        while j <= n:
            c[j][d] = float("inf")
            v[j].append(d)
            v[d].append(j)
            j += d
    print(ma*n-ford_fulkerson(0,n+1,c,e))
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return

#B
def B():

    return

#C
def C():
    def bfs(s,g,n):
        bfs_map = [-1 for i in range(n)]
        bfs_map[s] = 0
        q = deque()
        q.append(s)
        fin = False
        while q:
            x = q.popleft()
            for y in range(n):
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    if y == g:
                        fin = True
                        break
                    q.append(y)
            if fin:
                break

        if bfs_map[g] == -1:
            return [None,0]
        path = [None for i in range(bfs_map[g]+1)]
        m = float("inf")
        path[bfs_map[g]] = g
        y = g
        for i in range(bfs_map[g])[::-1]:
            for x in range(n+1):
                if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                    path[i] = x
                    if c[x][y] < m:
                        m = c[x][y]
                    y = x
                    break
        return [path,m]

    def ford_fulkerson(s,g,c,n):
        while 1:
            p,m = bfs(s,g,n)
            if not m:break
            for i in range(len(p)-1):
                c[p[i]][p[i+1]] -= m
                c[p[i+1]][p[i]] += m
        return sum(c[g])

    n = I()
    a = LI()
    e = n+2
    ma = 10**9
    c = [[0]*e for i in range(e)]
    for i in range(n):
        d = i+1
        j = 2*d
        c[0][d] = ma
        c[d][n+1] = ma-a[i]
        while j <= n:
            c[j][d] = float("inf")
            j += d
    print(ma*n-ford_fulkerson(0,n+1,c,e))
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
# Dinic's algorithm by @yaketake08
# https://tjkendev.github.io/procon-library/python/max_flow/dinic.html
from collections import deque
INF = 10**30
class Dinic:
	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.g[fr].append(forward)
		self.g[to].append(backward)

	def add_bidirectional_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.g[v1].append(edge1)
		self.g[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None]*self.n
		deq = deque([s])
		level[s] = 0
		g = self.g
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for w, cap, _ in g[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			w, cap, rev = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		g = self.g
		while self.bfs(s, t):
			*self.it, = map(iter, self.g)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow

n = int(input())
a = [-1] + list(map(int, input().split()))
d = Dinic(n+2)
s, t = 0, n+1

for i in range(1, n+1):
	if a[i] > 0:
		d.add_edge(i, t, a[i])
	elif a[i] < 0:
		d.add_edge(s, i, -a[i])
	for j in range(2*i, n+1, i):
		d.add_edge(i, j, INF)

res = d.flow(s, t)
print(sum([x for x in a if x>0]) - res)

Submission status: Accepted

Solution code:
def edmonds_karp(s, t, C):
    import copy
    import collections

    r = copy.deepcopy(c)
    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])

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