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

Solution (Python):
from collections import deque


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



def Edmonds_Karp(adjL, vSt, vEn):

    
    def BFS(vSt, vEn):
        prev = [-1] * numV
        prev[vSt] = None
        iE = [-1] * numV
        df = 0
        Q = deque([(vSt, float('inf'))])
        while Q:
            vNow, fNow = Q.popleft()
            if vNow == vEn:
                
                df = fNow
                break

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

        if df > 0:
            
            vNow = vEn
            while vNow != vSt:
                v0 = prev[vNow]
                e, iRev = iE[vNow]
                adjL[v0][e][1] -= df
                adjL[vNow][iRev][1] += df
                vNow = v0

        
        return df


    numV = len(adjL)
    MaximumFlow = 0
    while True:
        
        df = BFS(vSt, vEn)

        if df == 0:
            
            return MaximumFlow

        
        MaximumFlow += df


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

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

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


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

Solution (Python):

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



def Ford_Fulkerson(adjL, vSt, vEn):

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

        used[vNow] = True

        for i, (v2, cap, iRev) in enumerate(adjL[vNow]):
            if not used[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

        
        return 0


    numV = len(adjL)
    MaximumFlow = 0
    while True:
        
        used = [False] * numV
        df = DFS(vSt, vEn, float('inf'))

        if df == 0:
            
            return MaximumFlow

        
        MaximumFlow += df


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

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

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


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

Solution (Python):
import collections
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]
    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 add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in range(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

N = int(input())
*A, = map(int, input().split())
dinic = Dinic(N+2)

INF = 10**18

su = 0
for x in range(1, N+1):
    a = A[x-1]
    if a > 0:
        su += a
        dinic.add_edge(0, x+1, a)
    elif a < 0:
        dinic.add_edge(x+1, 1, -a)

for x in range(1, N+1):
    for y in range(x+x, N+1, x):
        dinic.add_edge(y+1, x+1, INF)

print(su - dinic.max_flow(0, 1))

Solution (Python):


from sys import stdin
from fractions import gcd	
from functools import reduce

def lcm(x, y):
    """The least common multiple of x and y."""
    return x * (y // gcd(x, y))

def multiples(t, N):
    """Set of multiples (<= N) of some x in t."""
    return set(i for x in t for i in range(x, N + 1, x))

def value(a, t):
    """The value of the jewels that are labeled a multiple of some x in t."""
    return sum(a[i - 1] for i in multiples(t, len(a)))

def remove(a, t):
    """Break all jewels that are labeled a multiple of some x in t."""
    for i in multiples(t, len(a)):
        a[i - 1] = 0

def tuples(m, N):
    """
    List of tuples over {m,...,N}.
    Each tuple t in the list satisfies that:
        the lcm of t is less than or equal to N, and
        t does not contain a proper multiple of some j in t.
    """
    if m > N: return [()]
    ts = tuples(m + 1, N)
    us = [(m,) + t for t in ts
          if reduce(lcm, t, m) <= N and all(j % m != 0 for j in t)]
    ts.extend(us)
    return ts

def solve(a):
    N = len(a)
    for t in tuples(1, N):
        if value(a, t) < 0: remove(a, t)
    return sum(a)

N = int(stdin.readline())
a = [int(w) for w in stdin.readline().split()]
if len(a) != N: raise
print(solve(a))

Solution (Python):


from sys import stdin
from fractions import gcd	
from functools import reduce

def lcm(x, y):
    """The least common multiple of x and y."""
    return x * (y // gcd(x, y))

def flatten(ls):
    """Flatten a list of lists."""
    return [x for l in ls for x in l]


def multiples(t, N):
    """Set of multiples (<= N) of some x in t."""
    return set(i for x in t for i in range(x, N + 1, x))

def value(a, t):
    """The value of the jewels that are labeled a multiple of some x in t."""
    return sum(a[i - 1] for i in multiples(t, len(a)))

def remove(a, t):
    """Break all jewels that are labeled a multiple of some x in t."""
    for i in multiples(t, len(a)):
        a[i - 1] = 0


def tuples(m, N):
    """
    [[m'-tuples over {1,2,3,...,N}] for 0 <= m' <= m].
    The lcm of the m-tuple is less than or equal to N.
    Each m-tuple does not contain a multiple of some j in the tuple.
    """
    if m == 0: return [[()]]
    ts = tuples(m - 1, N)
    if ts[-1] == []: return ts

    ls = []
    for t in ts[-1]:
        lc = reduce(lcm, t) if len(t) > 0 else 1
        mi = min(t)         if len(t) > 0 else N + 1
        for i in range(mi - 1, 0, -1):
            if lcm(lc, i) > N: continue
            if any(j % i == 0 for j in t): continue
            ls.append((i,) + t)  
    ts.append(ls)
    return ts

def solve(a):
    N = len(a)
    tl = flatten(tuples(N, N))
    
    tl.sort(key=lambda t: [-x for x in t])
    for t in tl:
        if value(a, t) < 0: remove(a, t)
    return sum(a)

N = int(stdin.readline())
a = [int(w) for w in stdin.readline().split()]
if len(a) != N: raise
print(solve(a))

Solution (Python):


from sys import stdin
from fractions import gcd	
from functools import reduce

def lcm(x, y):
  """The least common multiple of x and y."""
  return x * (y // gcd(x, y))

def tuples(m, N):
  """
  List of list of m'-tuples over {1,2,3,...,N} for 0 <= m' <= m.
  Every m-tuple does not contain a multiple of some j in the tuple.
  The lcm of the m-tuple is less than or equal to N.
  """
  if m == 0: return [[()]]
  ts = tuples(m - 1, N)
  if len(ts[-1]) == 0: return ts

  ls = []
  for t in ts[-1]:
    lc = reduce(lcm, t) if len(t) > 0 else 1
    mi = min(t)         if len(t) > 0 else N + 1
    for i in range(mi - 1, 0, -1):
      if any(j % i == 0 for j in t): continue
      if lcm(lc, i) > N: continue
      ls.append((i,) + t)
  ts.append(ls)
  return ts

def value(a, t):
  """
  Total value of the jewels that are labeled a multiple of x
  for some x in t.
  """
  used = [False for i in a]
  v = 0
  for x in t:
    for i in range(x - 1, len(a), x):
      if not used[i]:
        v = v + a[i]
        used[i] = True
  return v

def remove(a, t):
  """
  Break all jewels that are labeled a multiple of x for some x in t.
  """
  for x in t:
    for i in range(x - 1, len(a), x):
      a[i] = 0

def flatten(ls):
  """Flatten a list of lists."""
  return [x for l in ls for x in l]

def solve(a):
  n = len(a)
  tl = flatten(tuples(n, n))
  tl.sort(key=lambda t: [-x for x in t])
  for t in tl:
    if value(a, t) < 0: remove(a, t)
  return sum(a)

N = int(stdin.readline())
a = [int(w) for w in stdin.readline().split()]
if len(a) != N: raise
print(solve(a))

Solution (Python):
from collections import deque


class Dinic:
    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):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev 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
        for i, link in enumerate(self.links[v]):
            if i < self.progress[v]:
                continue
            self.progress[v] = i
            cap, to, rev = link
            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):
        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, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))


n = int(input())
an = list(map(int, input().split()))
mf = Dinic(n + 2)
max_value = 0
for i, a in enumerate(an):
    i += 1
    if a > 0:
        max_value += a
        mf.add_link(i, n + 1, a)
    else:
        mf.add_link(0, i, -a)
    for j in range(2 * i, n + 1, i):
        mf.add_link(i, j, float('inf'))
print(max_value - mf.max_flow(0, n + 1))

Solution (Python):


INF = float('inf');

def fulkerson(graph, src, sink):
    n = len(graph)

    matrix = [[0]*n for i in range(n)]
    bothDirGraph = [[] for i in range(n)]

    for nodeId, edges in enumerate(graph):
        for nodeId2, flowLimit in edges:
            matrix[nodeId][nodeId2] = flowLimit
            bothDirGraph[nodeId].append(nodeId2)
            bothDirGraph[nodeId2].append(nodeId)

    while True:
        path = findPath(bothDirGraph, matrix, src, sink)

        if path == None:
            break

        v = min(matrix[path[i]][path[i+1]] 
                for i in range(len(path)-1))

        for i in range(len(path)-1):
            node1 = path[i]
            node2 = path[i+1]
            
            matrix[node1][node2] -= v
            matrix[node2][node1] += v

    return (sum(c for _, c in graph[src]) - 
            sum(c for c in matrix[src]))


def findPath(bothDirGraph, matrix, src, sink):
    prevs = [None]*len(matrix)
    q = set([src])
    prevs[src] = src

    while len(q) > 0:
        node = q.pop()

        for nextNode in bothDirGraph[node]:
            if prevs[nextNode] == None and matrix[node][nextNode] > 0:
                prevs[nextNode] = node
                
                if nextNode == sink:
                    path = []
                    pathNode = sink

                    while pathNode != src:
                        path.append(pathNode)
                        pathNode = prevs[pathNode]

                    path.append(src)
                    return list(reversed(path))

                q.add(nextNode)

    return None
                    
def f(N, A):
    graph = [[] for i in range(N+2)]
    srcId = 0
    dstId = N+1

    for nodeId, a in enumerate(A, 1):
        if a < 0:
            graph[0].append((nodeId, -a))
        else:
            graph[nodeId].append((N+1, a))

        for k in range(2, N//nodeId+1):
            graph[nodeId].append((nodeId*k, INF))

    return (sum(filter(lambda a: a>0, A)) - 
            fulkerson(graph, 0, N+1))

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

    print(f(N, A))

if __name__ == '__main__':
    main()

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

def func(Bs):
    for x in range(N):
        if Bs[x] >= 0: continue
        if max(Bs[x::x + 1]) <= 0:
            Bs[x] = 0

func(As)

zs = [27, 29, 31, 33] + list(range(34, 51))
for x in zs:
    if sum(As[x - 1::x]) < 0:
        for i in range(x - 1, N, x):
            As[i] = 0

ns = [1, 2, 4, 8, 16, 32] + [3, 6, 9, 12, 18, 24, 27, 36, 48] \
    + [5, 10, 15, 20, 25, 30, 40, 45, 50] + [7, 14, 21, 28, 35, 42, 49] \
    + [11, 22, 33, 44] + [13, 26, 39] + [17, 34] + [19, 38] + [23, 46] \
    + [29, 31, 37, 41, 43, 47]

memo = {}
memo[tuple(As)] = sum(As)

cs = [n - 1 for n in ns if n <= N and n not in zs and As[n - 1] < 0]
for c in cs:
    for tupleA in list(memo.keys()):
        if tupleA[c] == 0:
            continue

        listA = list(tupleA)
        for x in range(c, N, c + 1):
            listA[x] = 0

        func(listA)
        memo[tuple(listA)] = sum(listA)

print(max(memo.values()))

Solution (Python):
class Ford_Fulkerson:

	def __init__(self, v, inf=float("inf")):
		self.V = v
		self.inf = inf
		self.G = [[] for _ in range(v)]
		self.used = [False for _ in range(v)]

	def addEdge(self, fm, to, cap):
		'''
		to:行き先
		cap:容量
		rev:反対側の辺
		'''
		self.G[fm].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
		self.G[to].append({'to':fm, 'cap':0, 'rev':len(self.G[fm])-1})


	def dfs(self, v, t, f):
		if v == t: return f
		self.used[v] = True

		for i in range(len(self.G[v])):
			e = self.G[v][i]
			if self.used[e["to"]] != True and e['cap'] > 0:
				d = self.dfs(e['to'], t ,min(f, e['cap']))
				if d > 0:
					e['cap'] -= d
					self.G[e['to']][e['rev']]['cap'] += d
					return d
		return 0

	def max_flow(self,s,t):
		flow = 0
		while True:
			self.used = [False for i in range(self.V)]
			f = self.dfs(s,t,self.inf)
			if f == 0: return flow
			flow += f



from sys import stdin, setrecursionlimit
def IL():return list(map(int, stdin.readline().split()))
 
setrecursionlimit(1000000)

def main():
	N = int(input())
	a = IL()
	d = Ford_Fulkerson(N+2)
	res = 0
	for i in range(N):
	    d.addEdge(N,i, max(0, -a[i]))
	    d.addEdge(i,N+1, max(0,a[i]))
	    res+=max(0,a[i])
	    t = 2*i+2
	    while t<=N:
	        d.addEdge(i,t-1,float('inf'))
	        t+=i+1
	print(res-d.max_flow(N,N+1))
	
	
if __name__ == "__main__": main()

Solution (Python):
class Dinic:

	def __init__(self, v, inf=float("inf")):
		self.V = v
		self.inf = inf
		self.G = [[] for _ in range(v)]
		self.level = [0 for _ in range(v)]
		self.iter = [0 for _ in range(v)]

	def addEdge(self, fm, to, cap):
		'''
		to:行き先
		cap:容量
		rev:反対側の辺
		'''
		self.G[fm].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
		self.G[to].append({'to':fm, 'cap':0, 'rev':len(self.G[fm])-1})


	
	def bfs(self, s):
		import queue
		self.level = [-1 for _ in range(self.V)]
		self.level[s] = 0
		que = queue.Queue()
		que.put(s)

		while not que.empty():
			v = que.get()
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if e['cap'] > 0 and self.level[e['to']] < 0:
					self.level[e['to']] = self.level[v] + 1
					que.put(e['to'])


	def dfs(self, v, t, f):
		if v == t: return f
		for i in range(self.iter[v], len(self.G[v])):
			self.iter[v] = i
			e = self.G[v][i]
			if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
				d = self.dfs(e['to'], t ,min(f,e['cap']))
				if d > 0:
					e['cap'] -= d
					self.G[e['to']][e['rev']]['cap'] += d
					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.iter = [0 for _ in range(self.V)]
			f = self.dfs(s,t,self.inf)
			while f > 0:
				flow += f
				f = self.dfs(s,t,self.inf)



from sys import stdin, setrecursionlimit
def IL():return list(map(int, stdin.readline().split()))
 
setrecursionlimit(1000000)

def main():
	N = int(input())
	a = IL()
	d = Dinic(N+2)
	res = 0
	for i in range(N):
	    d.addEdge(N,i, max(0, -a[i]))
	    d.addEdge(i,N+1, max(0,a[i]))
	    res+=max(0,a[i])
	    t = 2*i+2
	    while t<=N:
	        d.addEdge(i,t-1,float('inf'))
	        t+=i+1
	print(res-d.max_flow(N,N+1))
	
	
if __name__ == "__main__": main()

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 divisions(n):
    sq = int(math.sqrt(n)+1)
    d = collections.defaultdict(int)
    while n % 2 == 0:
        n //= 2
        d[2] += 1
    i = 3
    while n > 1 and sq >= i:
        if n % i == 0:
            n //= i
            d[i] += 1
        else:
            i += 2

    if n > 1:
        d[n] += 1

    r = [1]
    for k, v in d.items():
        for c in r[:]:
            for i in range(1,v+1):
                r.append(c*(k**i))

    return sorted(r)

def main():
    n = I()
    a = LI()
    s = set()
    for i in range(n,0,-1):
        d = divisions(i)
        ld = len(d)
        for j in range(1,2**ld):
            c = []
            ff = True
            for k in range(ld):
                if j & (1<<k):
                    f = True
                    for e in c:
                        if d[k] % e == 0:
                            f = False
                            ff = False
                            break
                    if f:
                        c.append(d[k])
                if not ff:
                    break
            if ff:
                s.add(tuple(c + [n+1]))
    b = sorted(list(s), reverse=True)
    for c in b:
        t = 0
        for j in range(1,n+1):
            f = False
            for e in c:
                if j%e == 0:
                    f = True
                    break
            if f:
                t += a[j-1]
        if t < 0:
            for j in range(1,n+1):
                f = False
                for e in c:
                    if j%e == 0:
                        f = True
                        break
                if f:
                    a[j-1] = 0

    return sum(a)



print(main())

Solution (Python):
n = int(input())
a = [0] + list(map(int, input().split()))
alive = [1 for i in range(n + 1)]
sol = sum(a)
while True:
    pot = []
    change = False
    for i in range(n, 0, -1):
        if a[i] >= 0 or alive[i] == 0:
            continue
        saldo = 0
        j = i
        while j <= n:
            saldo += alive[j] * a[j]
            j += i
        if saldo > 0:
            pot.append(i)
            continue
        change = True
        sol -= saldo
        j = i
        while j <= n:
            alive[j] = 0
            j += i
    if change:
        continue
    k = len(pot)
    for i in range(k):
        if change: break
        for j in range(i):
            saldo = 0
            for v in range(1, n + 1):
                if v % pot[i] == 0 or v % pot[j] == 0:
                    saldo += alive[v] * a[v]
            if saldo <= 0:
                change = True
                sol -= saldo
                for v in range(1, n + 1):
                    if v % pot[i] == 0 or v % pot[j] == 0:
                        alive[v] = 0
                break
    if not change:
        break
print(sol)