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: Wrong Answer

Solution code:
n = int(raw_input())

v = map(int, raw_input().split(' '))

res = sum(v)

i = len(v) - 1
while i >= 0:
	sum = 0

	j = i
	while j < len(v):
		sum += v[j]
		j += (i + 1)

	if sum < 0:
		res -= sum

		j = i

		while j < len(v):
			v[j] = 0
			j += (i + 1)

	i -= 1

print v
print res

Submission status: Wrong Answer

Solution code:
#!/opt/local/bin/python3

from sys import stdin

def solve(a):
  n = len(a)
  for i in range(n, 0, -1):
    s = 0
    for j in range(i, n + 1, i):
      s += a[j - 1]
    if s < 0:
      for j in range(i, n + 1, i):
        a[j - 1] = 0
  return sum(a)

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

Submission status: Wrong Answer

Solution code:
import copy
N = int(raw_input())
values = map(int, raw_input().split(" "))
values.insert(0, 0)
for i in range(N):
    table = N/(N-i)
    sumb = 0
    suma = 0
    for k in values:
        sumb += k
    aftervalue = copy.deepcopy(values)
    for t in range(table+1):
        aftervalue[(N-i)*t] = 0
    for k in aftervalue:
        suma += k
    if sumb < suma:
        values = aftervalue

sumb = 0
for k in values:
    sumb += k
print sumb

Submission status: Wrong Answer

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

a.insert(0, 0)
p = (n+1)*[0]
for i in range(1,n+1):
    for j in range(i,n+1,i):
        p[i] += a[j]
#print(p[1:n+1])

for m in range(1000000):
    flag = 0
    for i in range(n,0,-1):
        if p[i] < 0:
            flag = 1
            l = n // i * i
            for j in range(l,0,-i):
                if p[j] != 0:
                    for k in range(1,j+1):
                        if j % k == 0:
                            p[k] -= p[j]
            break
#    print(p[1:])
    if flag == 0:
        break
#print(p[1:n+1])
print(p[1])

Submission status: Wrong Answer

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

a.insert(0, 0)
p = (n+1)*[0]
for i in range(1,n+1):
    for j in range(i,n+1,i):
        p[i] += a[j]
#print(p[1:n+1])

for m in range(10000):
    flag = 0
    for i in range(n,0,-1):
        if p[i] < 0:
            flag = 1
            l = n // i * i
            for j in range(l,0,-i):
                if p[j] != 0:
                    for k in range(1,j+1):
                        if j % k == 0:
                            p[k] -= p[j]
            break
#    print(p[1:])
    if flag == 0:
        break
#print(p[1:n+1])
print(p[1])

Submission status: Wrong Answer

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

a.insert(0, 0)
p = (n+1)*[0]
for i in range(1,n+1):
    for j in range(i,n+1,i):
        p[i] += a[j]
#print(p[1:n+1])

for m in range(10000):
    flag = 0
    for i in range(n,0,-1):
        if p[i] < 0:
            flag = 1
            l = n // i * i
            for j in range(l,0,-i):
                if p[j] != 0:
                    for k in range(1,j+1):
                        if j % k == 0:
                            p[k] -= p[j]
            break
    print(p[1:])
    if flag == 0:
        break
#print(p[1:n+1])
print(p[1])

Submission status: Wrong Answer

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

a.insert(0, 0)
p = (n+1)*[0]
for i in range(1,n+1):
    for j in range(i,n+1,i):
        p[i] += a[j]
#print(p[1:n+1])

for m in range(10):
    flag = 0
    for i in range(n,0,-1):
        if p[i] < 0:
            flag = 1
            l = n // i * i
            for j in range(l,0,-i):
                if p[j] != 0:
                    for k in range(1,j+1):
                        if j % k == 0:
                            p[k] -= p[j]
            break
    if flag == 0:
        break
#print(p[1:n+1])
print(p[1])

Submission status: Wrong Answer

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

a.insert(0, 0)
p = (n+1)*[0]
for i in range(1,n+1):
    for j in range(i,n+1,i):
        p[i] += a[j]
#print(p[1:n+1])

for m in range(10):
    flag = 0
    for i in range(n,0,-1):
        if p[i] < 0:
            flag = 1
            l = n // i * i
            for j in range(l,0,-i):
                if p[j] != 0:
                    for k in range(1,j+1):
                        if j % k == 0:
                            p[k] -= p[j]
    if flag == 0:
        break
#print(p[1:n+1])
print(p[1])

Submission status: Wrong Answer

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

a.insert(0, 0)
p = (n+1)*[0]
for i in range(1,n+1):
    for j in range(i,n+1,i):
        p[i] += a[j]
#print(p[1:n+1])

for i in range(n,0,-1):
    if p[i] < 0:
        l = n // i * i
        for j in range(l,0,-i):
            if p[j] != 0:
                for k in range(1,j+1):
                    if j % k == 0:
                        p[k] -= p[j]
#print(p[1:n+1])
print(p[1])

Submission status: Wrong Answer

Solution code:
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):
		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=[-1]
    for i in IL():
        a.append(i)
        
    d = Ford_Fulkerson(102)
    s=0
    t=N+1
    
    _i=1
    _j=2
    while _i <= N:
        while _i*_j <=N:
            d.addEdge(_i, _i*_j, float("inf"))
            _j += 1
        _i += 1
    
    
    i=1
    while i <= N:
        d.addEdge(s,i,max(-a[i],0))
        d.addEdge(i,t,max(a[i],0))
        i+=1
    res = sum([max(i,0) for i in a])
 
    print(res - d.max_flow(s,t))
   
    
if __name__ == "__main__": main()

Submission status: Wrong Answer

Solution code:
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):
		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(102)
    s=N
    t=N+1
    
    for i in range(N):
        d.addEdge(s,i,max(-a[i],0))
        d.addEdge(i,t,max(a[i],0))
        x = i+1
        y=x+x
        for j in range(y,N+1):
            d.addEdge(x-1,y-1,float("inf"))
            
    res = sum([max(i,0) for i in a])
 
    print(res - d.max_flow(s,t))
   
    
if __name__ == "__main__": main()

Submission status: Wrong Answer

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


def main():
    N = int(input())
    a = IL()
    
    d = Ford_Fulkerson(102)
    s=N
    t=N+1
    for i in range(N):
        d.addEdge(s,i,max(-a[i],0))
        d.addEdge(i,t,max(a[i],0))
        x = i+1
        y=x+x
        for j in range(y,N+1):
            d.addEdge(x-1,y-1,float("inf"))
            
    res = sum([max(i,0) for i in a])
 
    print(res - d.max_flow(s,t))
    
if __name__ == "__main__": main()

Submission status: Wrong Answer

Solution code:
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
def IL():return list(map(int, stdin.readline().split()))
 
def main():
    N = int(input())
    a = IL()
    
    d = Ford_Fulkerson(102)
    s=N
    t=N+1
    for i in range(N):
        d.addEdge(s,i,max(-a[i],0))
        d.addEdge(i,t,max(a[i],0))
        x = i+1
        y=x+x
        for j in range(y,N+1):
            d.addEdge(x-1,y-1,float("inf"))
            
    res = sum([max(i,0) for i in a])
 
    print(res - d.max_flow(s,t))
    
if __name__ == "__main__": main()

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(s) for s in input().split()]

for i in list(reversed(range(N))):
    if sum([n for idx, n in enumerate(a) if (idx + 1) % (i + 1) == 0]) < 0:
        j = i + 1
        while j <= N:
            a[j - 1] = 0
            j += i + 1

print(sum(a))

Submission status: Wrong Answer

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

prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

def process(n, v, d):
  delta = v+1
  i = v
  d[v] = 0
  while i < N:
    if F[i]:
      d[v] += A[i]
    i += delta
  root = math.sqrt(delta)
  for p in prime:
    if p > root: break
    if delta % p != 0:
      continue
    process(n, delta/p-1, d)

i = N-1
while i >= 0:
  if not F[i]:
    i -= 1
    continue
  dic = {}
  process(i, i, dic)
  s = sorted(dic.items(), key=lambda x: x[1])
  #print s
  s = s[0]
  if s[1] < 0:
    n = s[0]
    delta = n+1
    while n < N:
      if F[n]:
        F[n] = False
        #i = max(i, n)
      n += delta
  i -= 1

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

Submission status: Wrong Answer

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

prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

def process(n, v, d):
  delta = v+1
  i = v
  d[v] = 0
  while i < N:
    if F[i]:
      d[v] += A[i]
    i += delta
  root = math.sqrt(v)
  for p in prime:
    if p > root: break
    if v % p != 0:
      continue
    process(n, v/p, d)

i = N-1
while i >= 0:
  if not F[i]:
    i -= 1
    continue
  dic = {}
  process(i, i, dic)
  s = sorted(dic.items(), key=lambda x: x[1])[0]
  if s[1] < 0:
    n = s[0]
    delta = n+1
    while n < N:
      if F[n]:
        F[n] = False
        #i = max(i, n)
      n += delta
  i -= 1

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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()
    b = []
    for i in range(n,0,-1):
        d = divisions(i)
        ld = len(d)
        for j in range(1,2**ld):
            c = []
            for k in range(ld):
                if j & (1<<k):
                    f = True
                    for e in c:
                        if d[k] % e == 0:
                            f = False
                            break
                    if f:
                        c.append(d[k])
            b.append((-1,tuple(c)))
    b = sorted(b, 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())

Submission status: Wrong Answer

Solution code:
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()
    b = []
    for i in range(n,0,-1):
        d = divisions(i)
        ld = len(d)
        for j in range(1,2**ld):
            c = []
            for k in range(ld):
                if j & (1<<k):
                    f = True
                    for e in c:
                        if d[k] % e == 0:
                            f = False
                            break
                    if f:
                        c.append(d[k])
            b.append((-len(c),tuple(c)))
    b = sorted(b, 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())

Submission status: Wrong Answer

Solution code:
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()
    b = []
    for i in range(n,0,-1):
        d = divisions(i)
        ld = len(d)
        for j in range(1,2**ld):
            c = []
            for k in range(ld):
                if j & (1<<k):
                    c.append(d[k])
            b.append((-len(c),tuple(c)))
    b = sorted(b, 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())

Submission status: Wrong Answer

Solution code:
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()
    for i in range(n,0,-1):
        d = divisions(i)
        ld = len(d)
        b = []
        for j in range(1,2**ld):
            c = []
            for k in range(ld):
                if j & (1<<k):
                    c.append(d[k])
            b.append((-len(c),tuple(c)))
        b = sorted(b, 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())

Submission status: Wrong Answer

Solution code:
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 main():
    n = I()
    a = LI()
    for i in range(n,0,-1):
        t = 0
        for j in range(i-1,n,i):
            t += a[j]
        if t < 0:
            for j in range(i-1,n,i):
                a[j] = 0
    return sum(a)



print(main())

Submission status: Wrong Answer

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


	# sからの最短距離をbfsで計算
	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
def IL():return list(map(int, stdin.readline().split()))

def main():
    N = int(input())
    a = IL()
    
    d = Dinic(102)
    s=N
    t=N+1
    for i in range(N):
        d.addEdge(s,i,max(-a[i],0))
        d.addEdge(i,t,max(a[i],0))
        x = i+1
        y=x+x
        for j in range(y,N+1):
            d.addEdge(x-1,y-1,float("inf"))
            
    res = sum([max(i,0) for i in a])

    print(res - d.max_flow(s,t))
    
if __name__ == "__main__": main()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from operator import add
import functools

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

#for i in range(math.floor(len(A)/2),len(A)):
#	if A[i]<0:
#		A[i]=0
#sum=[0]
j=N-1
while j>=0:
	#print(j)
	#print(A[j::j+1])
	if functools.reduce(add,A[j::j+1])<=0:
		i=j
		while i<N:
			A[i]=0
			i+=j+1
	j-=1
print(functools.reduce(add,A))

Submission status: Wrong Answer

Solution code:
import sys
import math
from operator import add
import functools

N=100
A=[i*(-1)**i for i in range(1,N+1)]

#for i in range(math.floor(len(A)/2),len(A)):
#	if A[i]<0:
#		A[i]=0
#sum=[0]
j=N-1
while j>=0:
	#print(j)
	hoge=[]
	#print(A[j::j+1])
	if functools.reduce(add,A[j::j+1])<=0:
		i=j
		while i<N:
			A[i]=0
			i+=j+1
	j-=1
print(functools.reduce(add,A))

Submission status: Wrong Answer

Solution code:
import sys
import math
from operator import add
import functools

N=100
A=[i*(-1)**i for i in range(1,N+1)]

#for i in range(math.floor(len(A)/2),len(A)):
#	if A[i]<0:
#		A[i]=0
#sum=[0]
j=N-1
while j>=0:
	#print(j)
	hoge=[]
	print(A[j::j+1])
	if functools.reduce(add,A[j::j+1])<=0:
		i=j
		while i<N:
			A[i]=0
			i+=j+1
	j-=1
print(functools.reduce(add,A))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
sum = 0
ans = 0
for i in range(n):
    x = n-i
    sum = 0
    for j in range(n//x):
        sum += a[x*(j+1)-1]
    if sum < 0:
        for k in range(n//x):
            a[x*(k+1)-1] = 0
for j in range(n):
    ans += a[j]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from operator import add
import functools

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

#for i in range(math.floor(len(A)/2),len(A)):
#	if A[i]<0:
#		A[i]=0
#sum=[0]
j=N-1
while j>=0:
	#print(j)
	#print(A[j::j+1])
	if functools.reduce(add,A[j::j+1])<0:
		i=j
		while i<N:
			A[i]=0
			i+=j+1
	j-=1
	#print(A)
print(functools.reduce(add,A))

Submission status: Wrong Answer

Solution code:
import sys
import math
from operator import add
import functools

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

for i in range(math.floor(len(A)/2),len(A)):
	if A[i]<0:
		A[i]=0
sum=[0]
j=N-1
while j>=0:
	#print(j)
	#print(A[j::j+1])
	if functools.reduce(add,A[j::j+1])<0:
		i=j
		while i<N:
			A[i]=0
			i+=j+1
	j-=1
	#print(A)
print(functools.reduce(add,A))

Submission status: Wrong Answer

Solution code:
import sys
import math
from operator import add
import functools

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

for i in range(math.floor(len(A)/2),len(A)):
	if A[i]<0:
		A[i]=0
sum=[0]
j=0
while j<N:
	if functools.reduce(add,A[j::j+1])<0:
		i=j
		while i<N:
			A[i]=0
			i+=j+1
	j+=1
print(functools.reduce(add,A))

Submission status: Wrong Answer

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

ms = [max(As[x::x + 1]) for x in range(N)]
for i, m in enumerate(ms):
    if m <= 0:
        for x in range(i, N, i + 1):
            As[x] = 0

memo = {}

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

    vs = [sum(tupleA[x::x + 1]) for x in range(N)]
    memo[tupleA] = vs[0]

    for i, v in enumerate(vs):
        if v >= 0:
            continue

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

        dfs(tuple(listA))


dfs(tuple(As))
print(max(memo.values()))

Submission status: Wrong Answer

Solution code:
import random
 
 
def check(iter, broken):
    iter_ans=0
    for j in iter:
        tmp_sum=0
        tmp_broken=set()
        for t in range(j, n, j+1):
            if t not in broken:
                tmp_sum+=aa[t]
                tmp_broken.add(t)
        # print(ans, j, tmp_broken, broken)
        if tmp_sum < 0:
            iter_ans -= tmp_sum
            broken.update(tmp_broken)
    return iter_ans
 
 
n=int(input())
aa=list(map(int,input().split()))
ans=sum(aa)
i=n//2
broken=set()
for j in range(i,n):
    if aa[j] < 0:
        ans -= aa[j]
        broken.add(j)
ccc=0
half=list(range(i))
for _ in range(10000):
    random.shuffle(half)
    c=check(half, broken.copy())
    ccc=max(ccc,c)
print(ans+ccc)