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:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


N, = rdi()
A = rdi()
A = [ 0 ] + A

for i in range(N/2+1, N+1):
        if A[i] < 0:
                A[i] = 0

flag = 1
while flag:
        flag = 0
        for i in range(N, 0, -1):
                if A[i] >= 0:
                        continue
                s = 0
                t = 0
                j = 2 * i
                while j <= N:
                        if A[j] > 0:
                                s += A[j]
                        else:
                                t += A[j]
                        j += i
                if s + A[i] <= 0:
                        j = i
                        while j <= N:
                                if A[j] != 0:
                                        flag = 1
                                A[j] = 0
                                j += i
                        continue
        if flag:
                continue
        for i in range(1, N+1):
                if A[i] >= 0:
                        continue
                s = 0
                t = 0
                j = 2 * i
                while j <= N:
                        if A[j] > 0:
                                s += A[j]
                        else:
                                t += A[j]
                        j += i
                if s + t + A[i] <= 0:
                        j = i
                        while j <= N:
                                if A[j] != 0:
                                        flag = 1
                                A[j] = 0
                                j += i
                        continue
                if flag:
                        break

print sum(A)

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

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

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 i % k == 0:
                        p[k] -= p[i]
#print(p[1:n])
print(p[1])

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


N, = rdi()
A = rdi()
A = [ 0 ] + A

for i in range(N/2+1, N+1):
        if A[i] < 0:
                A[i] = 0

flag = 1
while flag:
        flag = 0
        for i in range(N, 0, -1):
                if A[i] >= 0:
                        continue
                s = 0
                t = 0
                j = 2 * i
                while j <= N:
                        if A[j] > 0:
                                s += A[j]
                        else:
                                t += A[j]
                        j += i
                if s + A[i] <= 0:
                        j = i
                        while j <= N:
                                if A[j] != 0:
                                        flag = 1
                                A[j] = 0
                                j += i
                        continue
        if flag:
                continue
        for i in range(1, N+1):
                if A[i] >= 0:
                        continue
                s = 0
                t = 0
                j = 2 * i
                while j <= N:
                        if A[j] > 0:
                                s += A[j]
                        else:
                                t += A[j]
                        j += i
                if s + t + A[i] <= 0:
                        j = i
                        while j <= N:
                                if A[j] != 0:
                                        flag = 1
                                A[j] = 0
                                j += i
                        continue

print sum(A)

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(100):
    random.shuffle(half)
    c=check(half, broken.copy())
    ccc=max(ccc,c)
print(ans+ccc)

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 in range(N):
    if ms[i] <= 0:
        for x in range(i, N, i + 1):
            As[x] = 0

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


N, = rdi()
A = rdi()
A = [ 0 ] + A

for i in range(N/2+1, N+1):
        if A[i] < 0:
                A[i] = 0

flag = 1
while flag:
        flag = 0
        for i in range(N, 0, -1):
                if A[i] >= 0:
                        continue
                s = 0
                t = 0
                j = 2 * i
                while j <= N:
                        if A[j] > 0:
                                s += A[j]
                        else:
                                t += A[j]
                        j += i
                if s + A[i] <= 0:
                        j = i
                        while j <= N:
                                if A[j] != 0:
                                        flag = 1
                                A[j] = 0
                                j += i
                        continue
        if flag:
                continue
        for i in range(N, 0, -1):
                if A[i] >= 0:
                        continue
                s = 0
                t = 0
                j = 2 * i
                while j <= N:
                        if A[j] > 0:
                                s += A[j]
                        else:
                                t += A[j]
                        j += i
                if s + t + A[i] <= 0:
                        j = i
                        while j <= N:
                                if A[j] != 0:
                                        flag = 1
                                A[j] = 0
                                j += i
                        continue

print sum(A)

Submission status: Wrong Answer

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)]
    ms = [max(tupleA[x::x + 1]) for x in range(N)]
    vMin = min(vs)
    if vMin >= 0:
        return vs[0]

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

    vs = [sum(listA[x::x + 1]) for x in range(N)]

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

    return ans

print(dfs(As))

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
  ai = A[i]
  n = i
  d = i+1
  t = ai
  while n < N:
    if F[n]:
      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: Wrong Answer

Solution code:
N=int(raw_input())
A=map(int, raw_input().split())
B=[0 for i in range(N)]


while(1):
    for i in range(N):
        for j in range(1,N+1):
            if j%(i+1)==0:
                B[i]+=A[j-1]
    if min(B)<0:
        w = B.index(min(B))+1
        for i in range(1,N+1):
            if i%w==0:
                A[i-1]=0
    else:
        break
    B=[0 for i in range(N)]

print sum(A)

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
A=map(int, raw_input().split())
B=[0 for i in range(N)]


while(1):
    for i in range(N):
        for j in range(1,N+1):
            if j%(i+1)==0:
                B[i]+=A[j-1]
    if min(B)<0:
        w = B.index(min(B))+1
        for i in range(1,N+1):
            if i%w==0:
                A[i-1]=0
    else:
        break
    print A
    print B
    B=[0 for i in range(N)]

print sum(A)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=A[:]
while True:
  B=A[:]
  for j in range(N):
    for i in range(N,N-j-1,-1):
      w=0
      for k in range(N):
        if (k+1)%i==0:w+=B[k]
      if w<=0:#割ったほうがいい！
        for k in range(N):
          if (k+1)%i==0:B[k]=0
  if A==B:break
  else: A=B[:]
      
 
ans=0
for j in range(N):
  ans+=A[j]
print(ans)

Submission status: Wrong Answer

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

ls = []
for i in range(n, 0, -1):
    if a[i - 1] < 0:
        if n < i * i:
            s = 0
            for j in range(1, 101):
                if n < i * j:
                    break
                else:
                    s += a[i * j - 1]
            if s < 0:
                for j in range(1, 101):
                    if n < i * j:
                        break
                    else:
                        a[i * j - 1] = 0
        else:
            ls.append(i)
ans = sum(a)

for i in range(2**len(ls)):
    xs = []
    tmp = i
    idx = 0
    while 0 < tmp:
        xs.append(ls[idx])
        tmp //= 2
        idx += 1
    s = 0
    for j in range(1, n + 1):
        if all(map(lambda x: j % x != 0, xs)):
            s += a[j - 1]
    ans = max(ans, s)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
A=map(int, raw_input().split())
B=[0 for i in range(N)]


while(1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if j%i==0:
                B[i-1]+=A[i-1]
    if min(B)<0:
        w = B.index(min(B))+1
        for i in range(1,N+1):
            if i%w==0:
                A[i-1]=0
    else:
        break
    B=[0 for i in range(N)]

print sum(A)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=A[:]
while True:
  B=A[:]
  for i in range(N,0,-1):
    w=0
    for k in range(N):
      if (k+1)%i==0:w+=B[k]
    if w<0:#割ったほうがいい！
      for k in range(N):
        if (k+1)%i==0:B[k]=0
  if A==B:break
  else: A=B[:]
      
 
ans=0
for j in range(N):
  ans+=A[j]
print(ans)

Submission status: Wrong Answer

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

ls = []
for i in range(1, n + 1):
    if a[i - 1] < 0:
        if n < i * i:
            s = 0
            for j in range(1, 101):
                if n < i * j:
                    break
                else:
                    s += a[i * j - 1]
            if s < 0:
                for j in range(1, 101):
                    if n < i * j:
                        break
                    else:
                        a[i * j - 1] = 0
        else:
            ls.append(i)
ans = sum(a)

for i in range(2**len(ls)):
    xs = []
    tmp = i
    idx = 0
    while 0 < tmp:
        xs.append(ls[idx])
        tmp //= 2
        idx += 1
    s = 0
    for j in range(1, n + 1):
        if all(map(lambda x: j % x != 0, xs)):
            s += a[j - 1]
    ans = max(ans, s)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=A[:]
while True:
  B=A[:]
  for j in range(N):
    for i in range(N,N-j-1,-1):
      w=0
      for k in range(N):
        if (k+1)%i==0:w+=B[k]
      if w<0:#割ったほうがいい！
        for k in range(N):
          if (k+1)%i==0:B[k]=0
  if A==B:break
  else: A=B[:]
      
 
ans=0
for j in range(N):
  ans+=A[j]
print(ans)

Submission status: Wrong Answer

Solution code:
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)
fwd=check(range(i), broken.copy())
bkw=check(range(i-1,-1,-1), broken.copy())
print(ans+max(fwd,bkw))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
for z in range(10):
  for j in range(N):
    for i in range(N,N-j-1,-1):
      w=0
      for j in range(N):
        if (j+1)%i==0:w+=A[j]
      if w<0:#割ったほうがいい！
        for j in range(N):
          if (j+1)%i==0:A[j]=0
      
 
ans=0
for j in range(N):
  ans+=A[j]
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
for z in range(15):
  for j in range(N):
    for i in range(N,N-j-1,-1):
      w=0
      for j in range(N):
        if (j+1)%i==0:w+=A[j]
      if w<0:#割ったほうがいい！
        for j in range(N):
          if (j+1)%i==0:A[j]=0
      
 
ans=0
for j in range(N):
  ans+=A[j]
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
for j in range(N):
  for i in range(N,N-j-1,-1):
    w=0
    for j in range(N):
      if (j+1)%i==0:w+=A[j]
    if w<0:#割ったほうがいい！
      for j in range(N):
        if (j+1)%i==0:A[j]=0
      
 
ans=0
for j in range(N):
  ans+=A[j]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


N, = rdi()
A = rdi()
A = [ 0 ] + A

for i in range(N/2+1, N+1):
        if A[i] < 0:
                A[i] = 0

i = 1
while i <= N:
        if A[i] >= 0:
                i += 1
                continue
        s = 0
        j = 2 * i
        while j <= N:
                if A[j] > 0:
                        s += A[j]
                j += i
        if A[i] + s < 0:
                j = i
                while j <= N:
                        A[j] = 0
                        j += i
                i = 1
        else:
                i += 1

flag = 1
while flag:
        flag = 0
        for i in range(N, 0, -1):
                s = 0
                j = i
                while j <= N:
                        s += A[j]
                        j += i
                if s <= 0:
                        j = i
                        while j <= N:
                                if A[j] != 0:
                                        flag = 1
                                A[j] = 0
                                j += i

print sum(A)

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


N, = rdi()
A = rdi()
A = [ 0 ] + A

for i in range(N/2+1, N+1):
        if A[i] < 0:
                A[i] = 0

i = 1
while i <= N:
        if A[i] >= 0:
                i += 1
                continue
        s = 0
        j = 2 * i
        while j <= N:
                if A[j] > 0:
                        s += A[j]
                j += i
        if A[i] + s < 0:
                j = i
                while j <= N:
                        A[j] = 0
                        j += i
                i = 1
        else:
                i += 1

flag = 1
while flag:
        flag = 0
        for i in range(N, 0, -1):
                s = 0
                j = i
                while j <= N:
                        s += A[j]
                        j += i
                if s < 0:
                        j = i
                        while j <= N:
                                A[j] = 0
                                j += i
                        flag = 1

print sum(A)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
for j in range(100*N):
  for i in range(N,0,-1):
    w=0
    for j in range(N):
      if (j+1)%i==0:w+=A[j]
    if w<0:#割ったほうがいい！
      for j in range(N):
        if (j+1)%i==0:A[j]=0
      
 
ans=0
for j in range(N):
  ans+=A[j]
print(ans)

Submission status: Wrong Answer

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

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

for i in range(n-1,0,-1):
    if p[i] < 0:
        for j in range(1,i+1):
            if i % j == 0:
                p[j] -= p[i]

#print(p[1:n])
print(p[1])

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
src = list(map(int,input().split()))

if N == 1:
    print(max(0,src[0]))
    sys.exit()

exclude = set()
ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
for p in reversed(ps):
    a = p
    tmpsum = 0
    while a <= N:
        tmpsum += src[a-1]
        a += p
    if tmpsum < 0:
        exclude.add(p)

exclude = list(exclude)
ans = 0
for i,a in enumerate(src):
    skip = False
    for e in exclude:
        if (i+1) % e == 0:
            skip = True
            break
    if skip: continue
    ans += a
    
print(max(0,ans))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
for j in range(N):
  for i in range(N,0,-1):
    w=0
    for j in range(N):
      if (j+1)%i==0:w+=A[j]
    if w<0:#割ったほうがいい！
      for j in range(N):
        if (j+1)%i==0:A[j]=0
      
 
ans=0
for j in range(N):
  ans+=A[j]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


N, = rdi()
A = rdi()
A = [ 0 ] + A

for i in range(N/2+1, N+1):
        if A[i] < 0:
                A[i] = 0

i = 1
while i <= N:
        if A[i] >= 0:
                i += 1
                continue
        s = 0
        j = 2 * i
        while j <= N:
                if A[j] > 0:
                        s += A[j]
                j += i
        if A[i] + s < 0:
                j = i
                while j <= N:
                        A[j] = 0
                        j += i
                i = 1
        else:
                i += 1

for i in range(N, 0, -1):
        s = 0
        j = i
        while j <= N:
                s += A[j]
                j += i
        if s < 0:
                j = i
                while j <= N:
                        A[j] = 0
                        j += i

print sum(A)

Submission status: Wrong Answer

Solution code:
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)
for j in range(i-1, -1, -1):
    k=j+1
    tmp_sum=0
    tmp_broken=set()
    for t in range(j, n, k):
        if t not in broken:
            tmp_sum+=aa[t]
            tmp_broken.add(t)
    # print(ans, j, tmp_broken, broken)
    if tmp_sum < 0:
        ans -= tmp_sum
        broken.update(tmp_broken)
print(ans)

Submission status: Wrong Answer

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

for i in xrange(N-1, -1, -1):
  ai = A[i]
  n = i
  d = i+1
  t = ai
  while n < N:
    if F[n]:
      t += A[n]
    n += d
  if t < 0:
    n = i
    while n < N:
      F[n] = False
      n += d

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0] + list(map(int, input().split()))
alive = [1 for i in range(n + 1)]
sol = sum(a)
for i in range(n, 0, -1):
    if a[i] >= 0:
        continue
    saldo = 0
    j = i
    while j <= n:
        saldo += alive[j] * a[j]
        j += i
    if saldo > 0:
        continue
    sol -= saldo
    j = i
    while j <= n:
        alive[j] = 0
        j += i
print(sol)

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


N, = rdi()
A = rdi()
A = [ 0 ] + A

i = 1
while i <= N:
        if A[i] >= 0:
                i += 1
                continue
        s = 0
        j = i
        while j <= N:
                s += A[j]
                j += i
        if s < 0:
                j = i
                while j <= N:
                        A[j] = 0
                        j += i
                i = 1
        else:
                i += 1

print sum(A)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0] + list(map(int, input().split()))
alive = [1 for i in range(n + 1)]
sol = sum(a)
for i in range(n, 0, -1):
    saldo = 0
    j = i
    while j <= n:
        saldo += alive[j] * a[j]
        j += i
    if saldo >= 0:
        continue
    sol -= saldo
    j = i
    while j <= n:
        alive[j] = 0
        j += i
print(sol)

Submission status: Wrong Answer

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

while True:
    vs = [sum(As[x::x + 1]) for x in range(N)]

    vMin = min(vs)
    if vMin >= 0:
        break
    xMin = N - 1 - vs[::-1].index(vMin)

    for x in range(xMin, N, xMin + 1):
        As[x] = 0

print(vs[0])

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
for i in range(N,0,-1):
  w=0
  for j in range(N):
    if (j+1)%i==0:w+=A[j]
  if w<0:#割ったほうがいい！
    for j in range(N):
      if (j+1)%i==0:A[j]=0
      
 
ans=0
for j in range(N):
  ans+=A[j]
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from math import *
import random

def readln():
    return list(map(int,(input().split(" "))))

n = readln()[0]
a = readln()
a = [0] + a
ans = sum(a)
for i in range(1,n+1):
    index = n - i + 1
    t = 0
    for j in range(1,n):
        if i * j <= n :
            t = t - a[i*j]
    if t > 0:
        ans = ans + t
        for j in range(1,n):
            if i*j <= n:
                a[i*j] = 0

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
for i in range(N,0,-1):
  w=0
  for j in range(N):
    if (j+1)%i==0:w+=A[j]
  if w<=0:#割ったほうがいい！
    for j in range(N):
      if (j+1)%i==0:A[j]=0
      

ans=0
for j in range(N):
  ans+=A[j]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


N, = rdi()
A = rdi()
A = [ 0 ] + A

for i in range(N, 0, -1):
        s = 0
        j = i
        while j <= N:
                s += A[j]
                j += i
        if s < 0:
                j = i
                while j <= N:
                        A[j] = 0
                        j += i

print sum(A)

Submission status: Wrong Answer

Solution code:
n = input()
a = [0] + map(int, raw_input().split())

for i in range(1, n + 1)[::-1]:
	s = 0
	j = i
	while j <= n:
		s += a[j]
		j += i
	if s < 0:
		j = i
		while j <= n:
			a[j] = 0
			j += i

print sum(a)

Submission status: Time Limit Exceeded

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):
        self.level = [-1] * self.n
        q = deque()
        q.append([self.s, 0])
        while q:
            u, u_level = q.popleft()
            self.level[u] = u_level
            if u == self.t: return True
            for v, cap, _ in self.to[u]:
                if self.level[v] != -1: continue
                if cap == 0: continue
                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: Time Limit Exceeded

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):
        self.level = [-1] * self.n
        q = deque()
        q.append([self.s, 0])
        while q:
            u, u_level = q.popleft()
            self.level[u] = u_level
            if u == self.t: return True
            for v, cap, _ in self.to[u]:
                if self.level[v] != -1: continue
                if cap == 0: continue
                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(0,i,0)
            mf.add_edge(i,n+1,a)
            max_sum+=a
        else:
            mf.add_edge(0,i,-a)
            mf.add_edge(i,n+1,0)
    for i in range(1,n//2+1):
        for j in range(i*2,n+1,i):
            mf.add_edge(i,j,10**16)
    print(max_sum-mf.get_max_flow())

main()

Submission status: Time Limit Exceeded

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

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

cs = [i for i, A in enumerate(As) if A < 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()))