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: Time Limit Exceeded

Solution code:
N = int(input())
a = [int(n) for n in input().split()]
infty = 10**15
res = 0
edge = [[0]*(N+2) for _ in range(N+2)]

for i, t in enumerate(a):
    if t > 0:
        edge[i][N+1] = t
        res += t
    else:
        edge[N][i] = -t

for i in range(1, N+1):
    for j in range(2, N//i + 1):
        edge[i-1][i*j-1] = infty


def dfs(now):
    checked[now] = True
    if now == N+1:
        return 1
    for nx in range(N+2):
        if nx != now and edge[now][nx] > 0 and checked[nx] == False:
            if dfs(nx) > 0:
                edge[now][nx] -= 1
                edge[nx][now] += 1
                return 1
    return 0



# print(res)
while(True):
    checked = [False] * (N+2)
    checked[N] = True
    if dfs(N) > 0:
        res -= 1
    else:
        break

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [0] + list(map(int,input().split()))

def rec(X, l):

  v = sum(a for a,x in zip(A,X) if x)
  Y = X.copy()
  for i in range(l+1,N+1):
    if X[i]:
      for j in range(i,N+1,i):
        Y[j] = False
      v = max(rec(Y,i),v)
    Y = X.copy()
  return v

print(rec([False]+[True]*N,0))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = tuple(map(int, input().split()))

memo = set()

def dfs(tupleA):
    if tupleA in memo:
        return 0

    vs = [sum(tupleA[x::x + 1]) for x in range(N)]
    vMin = min(vs)
    if vMin >= 0:
        return vs[0]

    ans = 0
    for i in range(N):
        if vs[i] >= 0:
            continue
        listA = list(tupleA)
        for x in range(i, N, i + 1):
            listA[x] = 0
        tupleA2 = tuple(listA)
        ans = max(ans, dfs(tupleA2))
        memo.add(tupleA2)

    return ans

print(dfs(As))

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
A = map(int, raw_input().split())
F = [True] * 100
T = [0] * 100

i = N-1
while i >= 0:
  ai = A[i]
  n = i
  d = i+1
  t = ai
  while n < N:
    if not F[n]:
      break
    t += A[n]
    n += d
  if t < 0:
    n = i
    while n < N:
      F[n] = False
      i = max(i, n)
      n += d
  i -= 1

print sum(x*y for x,y in zip(A,F))

Submission status: Accepted

Solution code:
import networkx as nx

N=int(input())
*A,=map(int,input().split())
INF = 10**20

G = nx.DiGraph()
G.add_nodes_from(range(N+2))
for i in range(N):
  if A[i]<0:
    G.add_edge(0,i+1,capacity=-A[i])
    G.add_edge(i+1,N+1,capacity=0)
  else:
    G.add_edge(0,i+1,capacity=0)
    G.add_edge(i+1,N+1,capacity=A[i])
  
for i in range(1,N//2+1):
  for j in range(i,N+1,i):
    G.add_edge(i,j,capacity=INF)
    
flow_value,flow_dict = nx.maximum_flow(G,0,N+1)
print(sum(filter(lambda x: x>0,A))-flow_value)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

# 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):
        # 始点ノードidx，終点ノードidx，容量をinput
        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):
        # source/targetノードのidxを入力すると最大フロー（＝最小カット）が出力
        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 = [0] + list(map(int, input().split()))

dinic = Dinic(N+2)

for i in range(1,N+1):
    x = a[i]
    if x >= 0:
        dinic.add_edge(0, i, 0)
        dinic.add_edge(i, N+1, x)
    else:
        dinic.add_edge(0, i, abs(x))
        dinic.add_edge(i, N+1, 0)

for i in range(1,N+1):
    for j in range(2,N//i + 1):
        dinic.add_edge(i, j*i, INF)

print(sum([max(aa,0) for aa in a]) - dinic.flow(0, N+1))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Flow():
    def __init__(self, e, N):
        self.E = e
        self.N = N

    def max_flow(self, s, t):
        r = 0
        e = self.E

        def f(c, cap):
            v = self.v
            v[c] = 1
            if c == t:
                return cap
            for i in range(self.N):
                if v[i] or e[c][i] <= 0:
                    continue
                cp = min(cap, e[c][i])
                k = f(i, cp)
                if k > 0:
                    e[c][i] -= k
                    e[i][c] += k
                    return k
            return 0

        while True:
            self.v = [None] * self.N
            fs = f(s, inf)
            if fs == 0:
                break
            r += fs

        return r


def main():
    n = I()
    a = LI()

    s = n
    t = n + 1
    e = [[0] * (n+2) for _ in range(n+2)]
    for i in range(n):
        c = a[i]
        if c < 0:
            e[s][i] = -c
            ii = i + 1
            for j in range(ii*2, n+1, ii):
                e[i][j-1] = inf
        else:
            e[i][t] = c


    fl = Flow(e, n+2)
    r = fl.max_flow(s,t)

    return sum(map(lambda x: max(0,x), a)) - r

# start = time.time()
print(main())
# pe(time.time() - start)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
import networkx as nx
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    total = sum(a for a in A if a > 0)

    # minimum cut
    G = nx.DiGraph()
    G.add_nodes_from(range(1, n + 1))
    G.add_nodes_from(["source", "termination"])
    for i, a in enumerate(A, 1):
        if a >= 0:
            G.add_edge("source", i, capacity = 0)
            G.add_edge(i, "termination", capacity = a)
        else:
            G.add_edge("source", i, capacity = -a)
            G.add_edge(i, "termination", capacity = 0)

    for i in range(1, n + 1):
        for j in range(2 * i, n + 1, i):
            G.add_edge(i, j, capacity = INF)

    flow = nx.algorithms.flow.maximum_flow_value(G, "source", "termination")
    print(total - flow)
resolve()

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


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

score = 0
INF = float('inf')
graph = Dinic(n+2)

for i in range(n):
    if a[i]>0:
        graph.add_edge(i+1,n+1,a[i])
        score += a[i]
    elif a[i]<0:
        graph.add_edge(0,i+1,-a[i])

for i in range(1,n//2+1):
    for j in range(2*i,n+1,i):
        graph.add_edge(i,j,INF)

print(score-graph.flow(0,n+1))

Submission status: Accepted

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


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

score = 0
INF = float('inf')
graph = Dinic(n+2)

for i in range(n):
    if a[i]>0:
        graph.add_edge(i+1,n+1,a[i])
        score += a[i]
    elif a[i]<0:
        graph.add_edge(0,i+1,-a[i])

for i in range(1,n//2+1):
    for j in range(2*i,n+1,i):
        graph.add_edge(i,j,INF)

print(score-graph.flow(0,n+1))

Submission status: Accepted

Solution code:

"""
https://atcoder.jp/contests/arc085/tasks/arc085_c

"""

from collections import defaultdict
from collections import deque

def Ford_Fulkerson_Func(s,g,lines,cost):

    N = len(cost)
    ans = 0
    queue = deque([ [s,float("inf")] ])


    ed = [True] * N
    ed[s] = False

    route = [0] * N
    route[s] = -1

    while queue:

        now,flow = queue.pop()
        for nex in lines[now]:

            if ed[nex]: 
                flow = min(cost[now][nex],flow)
                route[nex] = now
                queue.append([nex,flow])
                ed[nex] = False

                if nex == g:
                    ans += flow
                    break
            
        else:
            continue
        break

    else:
        return False,ans


    t = g
    s = route[t]

    while s != -1:
        cost[s][t] -= flow
        if cost[s][t] == 0:
            lines[s].remove(t)

        if cost[t][s] == 0:
            lines[t].add(s)
        cost[t][s] += flow
        t = s
        s = route[t]

    return True,ans

def Ford_Fulkerson(s,g,lines,cost):

    ans = 0

    while True:
        fl,nans = Ford_Fulkerson_Func(s,g,lines,cost)

        if fl:
            ans += nans
            continue
        else:
            break
    
    return ans

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

S = N+1
T = N+2

lis = defaultdict(set)
cost = [[0] * (N+3) for i in range(N+3)]

for i in range(N):

    if a[i] > 0:
        lis[i+1].add(T)
        cost[i+1][T] += a[i]

    elif a[i] < 0:
        lis[S].add(i+1)
        cost[S][i+1] -= a[i]

for i in range(1,N+1):

    for j in range(i*2,N+1,i):

        lis[i].add(j)
        cost[i][j] += float("inf")


m = Ford_Fulkerson(S,T,lis,cost)

ss = 0
for i in range(N):
    if a[i] > 0:
        ss += a[i]
print (ss-m)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class Dinic():
    def __init__(self, source, sink):
        self.G = defaultdict(lambda:defaultdict(int))
        self.sink = sink
        self.source = source

    def add_edge(self, u, v, cap):
        self.G[u][v] = cap
        self.G[v][u] = 0

    def bfs(self):
        level = defaultdict(int)
        q = [self.source]
        level[self.source] = 1
        d = 1
        while q:
            if level[self.sink]:
                break
            qq = []
            d += 1
            for u in q:
                for v, cap in self.G[u].items():
                    if cap == 0:
                        continue
                    if level[v]:
                        continue
                    level[v] = d
                    qq += [v]
            q = qq
        self.level = level

    def dfs(self, u, f):
        if u == self.sink:
            return f
        for v, cap in self.iter[u]:
            if cap == 0 or self.level[v] != self.level[u] + 1:
                continue
            d = self.dfs(v, min(f, cap))
            if d:
                self.G[u][v] -= d
                self.G[v][u] += d
                return d
        return 0

    def max_flow(self):
        flow = 0
        while True:
            self.bfs()
            if self.level[self.sink] == 0:
                break
            self.iter = {u: iter(self.G[u].items()) for u in self.G}
            while True:
                f = self.dfs(self.source, INF)
                if f == 0:
                    break
                flow += f
        return flow

n = I()
s = 0
t = n + 1
dinic = Dinic(s, t)
A = LI()
total = 0
for i in range(1, n + 1):
    if A[i - 1] >= 0:
        total += A[i - 1]
        dinic.add_edge(s, i, 0)
        dinic.add_edge(i, t, A[i - 1])
    else:
        dinic.add_edge(s, i, -A[i - 1])
        dinic.add_edge(i, t, 0)
    for j in range(i * 2, n + 1, i):
        dinic.add_edge(i, j, INF)

print(total - dinic.max_flow())

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
import numpy as np
n=int(input())
a=[0]+[int(j)for j in input().split()]
graph=np.zeros((n+2,n+2),dtype=np.int64)
start,goal=0,n+1
for i,j in enumerate(a[1:],1):
    if j>=0:
        graph[start,i]=j
    else:
        graph[i,goal]=-j
for i in range(1,n+1):
    for j in range(2*i,n+1,i):
        graph[j,i]=10**18
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
print(sum(i for i in a if i>0)-max_flow(graph))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**10
mod = 10 ** 9 + 7

class Dinic:
    def __init__(self, v, inf=10**10):
        self.v = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [-1]*v  # 深さ
        self.ite = [0]*v  # DFSでの探索が済んでいるか
    def add_edge(self, fr, to, cap):
        self.G[fr].append([to, cap, len(self.G[to])])
        self.G[to].append([fr, 0, len(self.G[fr])-1])
    def bfs(self, s):  # BFSで深さ決定,sがstart
        self.level = [-1]*self.v  # 必要
        self.level[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            v = Q.popleft()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e[1]>0 and self.level[e[0]]<0: ###capacity>0かつtoの深さ未定
                    self.level[e[0]] = self.level[v]+1
                    Q.append(e[0])
    def dfs(self, v, t, f):  # DFSで増加パス探索,v開始、t終点、総フローf
        if v==t:
            return f
        for i in range(self.ite[v], len(self.G[v])):
            self.ite[v] = i
            e = self.G[v][i]
            if e[1]>0 and self.level[v]<self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d  # cap減少
                    self.G[e[0]][e[2]][1] += d  # 逆辺のcap増加
                    return d
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0:
                return flow
            self.ite = [0]*self.v  # DFSでの探索が済んでいるか否か
            f = self.dfs(s,t,self.inf)
            while f>0:
                flow += f
                f = self.dfs(s,t,self.inf)

N = INT()
a = LIST()

D = Dinic(N+2)
s = 0
t = N+1

rw = 0

for i, x in enumerate(a):
    if x <= 0:  # そのまま罰金
        D.add_edge(s, i+1, -x)
    elif x > 0:  # あらかじめxもらっておき，これが破壊されるとxの罰金，
        D.add_edge(i+1, t, x)
        rw += x
    for j in range(2*(i+1), N+1, i+1):  # 「iが破壊かつjが非破壊」はだめ
        D.add_edge(i+1, j, INF)

print(rw - D.max_flow(s, t))

Submission status: Accepted

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

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

jew=Dinic(N+2)
ans=0
for i in range(N):
    if a[i]>=0:
        ans+=a[i]
        jew.add_edge(0,i+1,a[i])
    else:
        jew.add_edge(i+1,N+1,-a[i])

inf=10**15
for i in range(1,N+1):
    for j in range(1,N//i+1):
        jew.add_edge(i*j,i,inf)

f=jew.flow(0,N+1)
print(ans-f)

Submission status: Accepted

Solution code:
N=int(input())
alist=[0]+list(map(int,input().split()))
xlist=list(range(1,N+1))
#print(alist,xlist)

# Ford-Fulkerson algorithm
class FordFulkerson:
  def __init__(self, vlist):
    self.G = {}
    for v in vlist:
      self.G[v] = []

  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 dfs(self, v, t, f):
    if v == t:
      return f
    used = self.used
    used[v] = True
    for e in self.G[v]:
      w, cap, rev = e
      if cap and not used[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
    f = INF = 10**9 + 7
    while f:
      self.used = {}
      for v in self.G:
        self.used[v]=False
      f = self.dfs(s, t, INF)
      flow += f
    return flow
  
asum_pos=0  
## 点数N、辺数M、始点s、終点t
ff = FordFulkerson(range(N+2))
for i in range(1,N+1):
  a=alist[i]
  if a<=0:
    ff.add_edge(0,i,-a)
  else:
    ff.add_edge(i,N+1,a)
    asum_pos+=a

for i in range(1,N+1):
  for j in range(2*i,N+1,i):
    ff.add_edge(i,j,float("inf"))

penalty=ff.flow(0,N+1)
print(asum_pos-penalty)

Submission status: Accepted

Solution code:
N=int(input())
alist=[0]+list(map(int,input().split()))
xlist=list(range(1,N+1))
#print(alist,xlist)

# Ford-Fulkerson algorithm
class FordFulkerson:
  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 dfs(self, v, t, f):
    if v == t:
      return f
    used = self.used
    used[v] = 1
    for e in self.G[v]:
      w, cap, rev = e
      if cap and not used[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
    f = INF = 10**9 + 7
    N = self.N 
    while f:
      self.used = [0]*N
      f = self.dfs(s, t, INF)
      flow += f
    return flow

asum_pos=0  
## 点数N、辺数M、始点s、終点t
ff = FordFulkerson(N+2)
for i in range(1,N+1):
  a=alist[i]
  if a<=0:
    ff.add_edge(0,i,-a)
  else:
    ff.add_edge(i,N+1,a)
    asum_pos+=a

for i in range(1,N+1):
  for j in range(2*i,N+1,i):
    ff.add_edge(i,j,float("inf"))

penalty=ff.flow(0,N+1)
print(asum_pos-penalty)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class Dinic():
    def __init__(self, source, sink):
        self.G = defaultdict(lambda:defaultdict(int))
        self.sink = sink
        self.source = source

    def add_edge(self, u, v, cap):
        self.G[u][v] = cap
        self.G[v][u] = 0

    def bfs(self):
        level = defaultdict(int)
        q = [self.source]
        level[self.source] = 1
        d = 1
        while q:
            if level[self.sink]:
                break
            qq = []
            d += 1
            for u in q:
                for v, cap in self.G[u].items():
                    if cap == 0:
                        continue
                    if level[v]:
                        continue
                    level[v] = d
                    qq += [v]
            q = qq
        self.level = level

    def dfs(self, u, f):
        if u == self.sink:
            return f
        for v, cap in self.iter[u]:
            if cap == 0 or self.level[v] != self.level[u] + 1:
                continue
            d = self.dfs(v, min(f, cap))
            if d:
                self.G[u][v] -= d
                self.G[v][u] += d
                return d
        return 0

    def max_flow(self):
        flow = 0
        while True:
            self.bfs()
            if self.level[self.sink] == 0:
                break
            self.iter = {u: iter(self.G[u].items()) for u in self.G}
            while True:
                f = self.dfs(self.source, INF)
                if f == 0:
                    break
                flow += f
        return flow

n = I()
A = LI()
score = 0
s = 0
t = n + 1
dinic = Dinic(s, t)
for i in range(1, n + 1):
    if A[i - 1] > 0:
        score += A[i - 1]
        dinic.add_edge(s, i, 0)
        dinic.add_edge(i, t, A[i - 1])
    else:
        dinic.add_edge(s, i, -A[i - 1])
        dinic.add_edge(i, t, 0)
    ret = i
    while ret + i <= n:
        ret += i
        dinic.add_edge(i, ret, INF)


print(score - dinic.max_flow())