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:
#!/usr/bin/env python3

import math

def gcd(a, b):
    if a < b:
        a, b = b, a
    q, r = a, b
    while r:
        q, r = r, q % r

    return q


def lcm(a, b):
    return a * b // gcd(a, b)


def solve(n, a):
    for i in range(n, n // 2, -1):
        a[i] = max(a[i], 0)

    r = max(sum(a), 0)

    m = int(math.sqrt(n))

    d = []
    for i in range(m + 1, n // 2 + 1):
        for j in range(i + 1, n // 2 + 1):
            if gcd(i, j) == i:
                continue
            l = lcm(i, j)
            if l <= n:
                d.append((i, j, l))

    for x in range(2 ** (m - 1)):
        b = a.copy()
        for i in range(m - 1):
            if x & (2 ** i):
                for j in range(i + 2, n + 1, i + 2):
                    b[j] = 0
        for i, j, l in d:
            if sum(b[i: n + 1: i]) + sum(b[j: n + 1: j]) - sum(b[l: n + 1: l]) < 0:
                for k in range(i, n + 1, i):
                    b[k] = 0
                for k in range(j, n + 1, j):
                    b[k] = 0
        for i in range(n // 2, m, -1):
            if sum(b[i: n + 1: i]) < 0:
                for j in range(i, n + 1, i):
                    b[j] = 0
        r = max(sum(b), r)

    return r


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = [0] + a

    print(solve(n, a))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import math

def gcd(a, b):
    if a < b:
        a, b = b, a
    q, r = a, b
    while r:
        q, r = r, q % r

    return q


def lcm(a, b):
    return a * b // gcd(a, b)


def solve(n, a):
    r = max(sum(a), 0)

    m = int(math.sqrt(n))

    d = []
    for i in range(m + 1, n // 2 + 1):
        for j in range(i + 1, n // 2 + 1):
            if gcd(i, j) == i:
                continue
            l = lcm(i, j)
            if l <= n:
                d.append((i, j, l))

    for x in range(2 ** (m - 1)):
        b = a.copy()
        for i in range(m - 1):
            if x & (2 ** i):
                for j in range(i + 2, n + 1, i + 2):
                    b[j] = 0
        for i in range(n, m, -1):
            if sum(b[i: n + 1: i]) < 0:
                for j in range(i, n + 1, i):
                    b[j] = 0
        for i, j, l in d:
            if sum(b[i: n + 1: i]) + sum(b[j: n + 1: j]) - sum(b[l: n + 1: l]) < 0:
                for k in range(i, n + 1, i):
                    b[k] = 0
                for k in range(j, n + 1, j):
                    b[k] = 0
        r = max(sum(b), r)

    return r


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = [0] + a

    print(solve(n, a))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import math

def solve(n, a):
    r = max(sum(a), 0)

    m = int(math.sqrt(n))
    for x in range(2 ** (m - 1)):
        b = a.copy()
        for i in range(m - 1):
            if x & (2 ** i):
                for j in range(i + 2, n + 1, i + 2):
                    b[j] = 0
        for i in range(n, m, -1):
            if sum(b[i: n + 1: i]) < 0:
                for j in range(i, n + 1, i):
                    b[j] = 0
        r = max(sum(b), r)

    return r


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = [0] + a

    print(solve(n, a))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

total = sum(a)
prev_total = 0
while True:

    if total == prev_total:
        break

    prev_total = total

    for i in range(len(a)):
        index = N-i-1
        if a[index] >= 0:
            continue

        sub_total = 0
        for j in range(index, N, index+1):
            # print(j)
            sub_total += a[j]

        if sub_total < 0:
            # print("YES")
            total -= sub_total
            for j in range(index, N, index+1):
                a[j] = 0

print(total)

Submission status: Wrong Answer

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

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

total = sum(a)

for i in range(len(a)):
    index = N-i-1
    if a[index] >= 0:
        continue

    sub_total = 0
    for j in range(index, N, index+1):
        # print(j)
        sub_total += a[j]

    if sub_total < 0:
        # print("YES")
        total -= sub_total
        for j in range(index, N, index+1):
            a[j] = 0

print(total)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(200000)
n = int(input())
houseki = list(map(int,input().split()))
g = [[] for i in range(n+2)]
INF = float("inf")
MAX = 0
for i in range(n):
  if houseki[i] <= 0:
    g[0].append([i+1,-houseki[i],len(g[i+1])])
    g[i+1].append([0,0,len(g[0])-1])
  else:
    g[n+1].append([i+1,houseki[i],len(g[i+1])])
    g[i+1].append([n+1,0,len(g[n+1])-1])
    MAX += houseki[i]
  j = (i+1)*2
  while j <= n:
    g[i+1].append([j,INF,len(g[j])])
    g[j].append([i+1,0,len(g[i+1])-1])
    j += i+1
def bfs(s,t):
  global level
  que = deque([s])
  level[s] = 0
  while que:
    v = que.popleft()
    lv = level[v] +1
    for y, cap, rev in g[v]:
      if cap and level[y] is None:
        level[y] = lv
        que.append(y)
  return level[t] if level[t] else 0
def dfs(x,t,f):
  if x == t:
    return f
  for j in range(it[x],len(g[x])):
    it[x] = j
    y, cap, rev = g[x][j]
    if cap and level[x] < level[y]:
      d = dfs(y,t,min(f,cap))
      if d:
        g[x][j][1] -= d
        g[y][rev][1] += d
        return d
  return 0
 
flow = 0
f = INF = float("inf")
level = [None]*(n+2)
while bfs(0,n+1):
  it = [0]* (n+2)
  f = INF
  while f:
    f = dfs(0,n+2,INF)
    flow += f
  level = [None]*n
print(MAX-flow)

Submission status: Wrong Answer

Solution code:
import math
def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n //= m
        return c, n
    #
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff
def divisor_sub(p, q):
    a = []
    for i in range(0, q + 1):
        a.append(p ** i)
    return a

def divisor(n):
    if n == 1:
      return([1])
    xs = factorization(n)
    ys = divisor_sub(xs[0][0], xs[0][1])
    for p, q in xs[1:]:
        ys = [x * y for x in divisor_sub(p, q) for y in ys]
    return sorted(ys)
n = int(input())
a = list(map(int,input().split()))
for i in range(n,0,-1):
  b = divisor(i)
  c = [0]* len(b)
  for j in range(len(b)):
      x = b[j]
      ke = 0
      while x <= n:
        ke += a[x-1]
        x+= b[j]
      c[j] = ke
  ind = c.index(min(c))
  if c[ind] <0:
    x = b[ind]
    while x <= n:
      a[x-1] = 0
      x+= b[ind]  
print(sum(a))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
for i in range(n,0,-1):
  x = i
  ke = 0
  while x <= n:
    ke += a[x-1]
    x+=i
  if ke < 0:
    x = i
    while x <= n:
      a[x-1] = 0
      x+=i
print(sum(a))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
for i in range(1,N+1)[::-1]:
  if sum([a for n,a in enumerate(A) if (n+1)%i==0])<0:
    for k in range(1,N//i+1):
      A[k*i-1]=0
print(sum(A))

Submission status: Wrong Answer

Solution code:


n=int(input())
A=list(map(int,input().split()))
A.insert(0,0)

for i in range(n,1+n//12,-1):
    tmp_sum=0
    j=i
    while(1):
        tmp_sum+=A[j]
        j+=i
        if(j>=n+1):
            break
    if(tmp_sum<=0):
        j=i
        while(1):
            A[j]=0
            j+=i
            if(j>=n+1):
                break
    
bit=0
ans=[]
while(1):
    B=[A[i] for i in range(n+1)]
    for i in range(1+n//12):
        if( bit & 1<<i):
            j=i+1
            while(1):
                if(j>=n+1):
                    break
                B[j]=0
                j+=i+1
    ans.append(sum(B))
    bit+=1
    if(bit >= 2**(1+n//12)):
        break
print(max(ans))

Submission status: Wrong Answer

Solution code:


n=int(input())
A=list(map(int,input().split()))
A.insert(0,0)

for i in range(n,n//12,-1):
    tmp_sum=0
    j=i
    while(1):
        tmp_sum+=A[j]
        j+=i
        if(j>=n+1):
            break
    if(tmp_sum<=0):
        j=i
        while(1):
            A[j]=0
            j+=i
            if(j>=n+1):
                break
    
bit=0
ans=[]
while(1):
    B=[A[i] for i in range(n+1)]
    for i in range(max([n//12,1])):
        if( bit & 1<<i):
            j=i+1
            while(1):
                if(j>=n+1):
                    break
                B[j]=0
                j+=i+1
    ans.append(sum(B))
    bit+=1
    if(bit >= 2**(max([n//12,1]))):
        break
print(max(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
c,ans = [1]*n,0
def f(x):
	num = 0
	for i in range(x,n+1,x):
		if c[i-1]: num+=a[i-1]
	if num<0:
		for i in range(x,n+1,x): c[i-1] = 0
for i in range(n,0,-1): f(i)
for i in range(n):
	if c[i]: ans+=a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
c,ans = [1]*n,sum(a)
def f(x):
	num = 0
	for i in range(x,n+1,x):
		if c[i-1]: num+=a[i-1]
	if num<0:
		for i in range(x,n+1,x): c[i-1] = 0
		return num
	else: return 0
for i in range(n,0,-1): ans-=f(i)
print(ans)

Submission status: Wrong Answer

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

member = {n : {i * n for i in range(1, N//n + 1)} for n in range(2, N//2 + 1)}
gain = [True] * (N + 1)
A = [0] + A

def f():
    S = sum(A)
    for n in range(N//2 + 1, N + 1):
        if A[n] < 0:
            S -= A[n]
            gain[n] = False
    
    for n in range(N//2, 1, -1):
        s = 0
        temp = set()
        for m in member[n]:
            if gain[m]:
                s += A[m]
                temp.add(m)
            
        if s < 0:
            S -= s
            for m in temp:
                gain[m] = False
        
    print(S)

for a in A:
    if a > 0:
        f()
        break
else:
    print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque
class Dinic:
    def __init__(self,number):
        self.table = [[0]*(number) for i in range(number)]
        self.n=number
    
    def add(self,x,y,f):
        self.table[x][y]=f
    
    def bfs(self,x):
        self.visit[x]=0
        h=deque()
        h.append(x)
        while h:
            y=h.popleft()
            for i in range(self.n):
                if self.visit[i]==-1 and self.table[y][i]>0:
                    self.visit[i]=self.visit[y]+1
                    h.append(i)
        return 0
    
    def dinic(self,s,t,f):
        if s==t:
            return f
        for i in range(self.n):
            if self.visit[i]>self.visit[s] and self.table[s][i]>0:
                df = self.dinic(i,t,min(f,self.table[s][i]))
                if df>0:
                    self.table[s][i]-=df
                    self.table[i][s]+=df
                    return df
        return 0
    
    def flow(self,s,t):
        ans=0
        inf=10**20
        while True:
            self.visit=[-1]*(self.n)
            self.bfs(s)
            if self.visit[t]==-1:
                break
            while True:
                df=self.dinic(s,t,inf)
                if df==0:
                    break
                ans+=df
        return ans
N=int(input())
P=[int(i) for i in input().split()]
inf=10**20
maxflow=Dinic(N+2)
for i in range(1,N+1):
    if P[i-1]>0:
        maxflow.add(i,N+1,P[i-1])
    else:
        maxflow.add(0,i,-P[i-1])
    for j in range(2*i,N+1,i):
        maxflow.add(i,j,inf)
ans=maxflow.flow(0,N+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
while True:
  broken = [0, 0]
  for b in range(1, N + 1):
    B = sum([A[i] for i in range(N) if (i + 1) % b == 0])
    if B < broken[0]:
      broken = [B, b]
  if broken[1]:
    for i in range(1, N // broken[1] + 1):
      A[broken[1] * i - 1] = 0
  else:
    break
print(sum(A))

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

INF = 1 << 60

def main():
  N = read()
  A = reads()
  offset = sum(a for a in A if a > 0)
  
  edges = [[] for _ in range(N+2)] # 0: source, N+1: target
  for i in range(1, N+1):
    a = A[i-1]
    if a <= 0:
      edges[0].append((i, -a))
    else:
      edges[i].append((N+1, a))
    for j in range(2*i, N+1, i):
      edges[i].append((j, INF))
  ans = offset - max_flow(edges, 0, N+1)
  print(ans)

def bfs(edges, cap, s):
  N = len(edges)
  level = [-1] * N; level[s] = 0
  que = deque([s])
  while len(que) > 0:
    u = que.popleft()
    for v, _ in edges[u]:
      if cap[u][v] > 0 and level[v] < 0:
        level[v] = level[u] + 1
        que.append(v)
  return level

def dfs(edges, cap, itr, level, u, t, f):
  if u == t: return f
  for i in range(itr[u], len(edges[u])):
    itr[u] = i
    v, _ = edges[u][i]
    if cap[u][v] > 0 and level[u] < level[v]:
      d = dfs(edges, cap, itr, level, v, t, min(f, cap[u][v]))
      if d > 0:
        cap[u][v] -= d
        cap[v][u] += d
        return d
  return 0

def max_flow(edges, s, t):
  N = len(edges)
  cap = [[0] * N for _ in range(N)]
  for u in range(N):
    for v, c in edges[u]:
      cap[u][v] += c

  flow = 0
  while True:
    level = bfs(edges, cap, s)
    if level[t] < 0: return flow
    itr = [0] * N
    while True:
      f = dfs(edges, cap, itr, level, s, t, INF)
      if f <= 0: break
      flow += f

main()

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

INF = 1 << 60

def main():
  N = read()
  A = reads()
  offset = sum(a for a in A if a > 0)
  
  edges = [[] for _ in range(N+2)] # 0: source, N+1: target
  for i in range(1, N+1):
    a = A[i-1]
    if a <= 0:
      edges[0].append((i, -a))
    else:
      edges[i].append((N+1, a))
    for j in range(2*i, N+1, i):
      edges[i].append((j, INF))
  ans = offset - max_flow(edges, 0, N+1)
  print(ans)

def max_flow(edges, s, t):
  n = len(edges)
  flow = [[0] * n for _ in range(n)]
  capacity = [[0] * n for _ in range(n)]
  for u in range(n):
    for v, weight in edges[u]:
      capacity[u][v] = weight

  def residue(s,t):
    return capacity[s][t] - flow[s][t]
  
  total = 0
  while True:
    que = deque([s])
    prev = [-1] * n; prev[s] = s
    while len(que) > 0 and prev[t] < 0:
      u = que.popleft()
      for v, weight in edges[u]:
        if prev[v] < 0 and residue(u, v) > 0:
          prev[v] = u
          que.append(v)
    if prev[t] < 0:
      return total
    
    def revwalk(x):
      j = x    
      while prev[j] != j:
        yield j
        j = prev[j]

    inc = INF
    for j in revwalk(t):
      inc = min(inc, residue(prev[j], j))
    for j in revwalk(t):
      inc = min(inc, residue(prev[j], j))
      flow[prev[j]][j] += inc; flow[j][prev[j]] -= inc
    total += inc

main()

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

INF = 1 << 60

def main():
  N = read()
  A = reads()
  offset = sum(a for a in A if a > 0)
  
  edges = [[] for _ in range(N+2)] # 0: source, N+1: target
  for i in range(1, N+1):
    a = A[i-1]
    if a > 0:
      edges[0].append((i, a))
      edges[i].append((N+1, 0))
    else:
      edges[0].append((i, 0))
      edges[i].append((N+1, -a))
    for j in range(2*i, N+1, i):
      edges[j].append((i, INF))
  
  ans = offset - max_flow(edges, 0, N+1)
  print(ans)

def max_flow(edges, s, t):
  n = len(edges)
  flow = [[0] * n for _ in range(n)]
  capacity = [[0] * n for _ in range(n)]
  for u in range(n):
    for v, weight in edges[u]:
      capacity[u][v] = weight

  def residue(s,t):
    return capacity[s][t] - flow[s][t]
  
  total = 0
  while True:
    que = deque([s])
    prev = [-1] * n; prev[s] = s
    while len(que) > 0 and prev[t] < 0:
      u = que.popleft()
      for v, weight in edges[u]:
        if prev[v] < 0 and residue(u, v) > 0:
          prev[v] = u
          que.append(v)
    if prev[t] < 0:
      return total
    
    def revwalk(x):
      j = x    
      while prev[j] != j:
        yield j
        j = prev[j]

    inc = INF
    for j in revwalk(t):
      inc = min(inc, residue(prev[j], j))
    for j in revwalk(t):
      inc = min(inc, residue(prev[j], j))
      flow[prev[j]][j] += inc; flow[j][prev[j]] -= inc
    total += inc

main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

N=int(input())
A=[int(x) for x in input().split()]

def solve(n):
  cnt=1
  res=[]
  while cnt*n<=N:
    res.append(A[cnt*n-1])
    cnt+=1
  ans=list(accumulate(res))
  if max(ans)>=0:
    return
  else:
    for i in range(1,cnt):
      A[n*i-1]=0
    return

for i in range(N-1,-1,-1):
  if A[i] < 0:
    solve(i+1)

print(sum(A))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

N=int(input())
A=[int(x) for x in input().split()]
ans=0

def solve(n):
  cnt=1
  res=[]
  while cnt*n<=N:
    res.append(A[cnt*n-1])
    cnt+=1
  ans=list(accumulate(res))
  if max(ans)>=0:
    return True
  else:
    for i in range(1,cnt):
      A[n*i-1]=0
    return False

for i in range(N):
  if A[i] >= 0:
    ans+=A[i]
  else:
    if solve(i+1):
      ans+=A[i]

print(ans)

Submission status: Wrong Answer

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


N = int(input())
a = list(map(int,input().split()))
b = [1 for i in range(N)]

Score = 0 

for x in range(N):
	s = 0
	for i in range(x+1):
		if ((N-x+i)%(N-x)==0) and (b[N-x+i-1] == 1):
			s += a[N-x+i-1]
	if s < 0:
		for j in range(x+1):
			if ((N-x+j)%(N-x)==0) and (b[N-x+j-1] == 1):
				b[N-x+j-1] = 0

c = [x * y for (x, y) in zip(a, b)]

for i in range(N):
	Score += c[i]

print(Score)

Submission status: Wrong Answer

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


N = int(input())
a = list(map(int,input().split()))
b = [1 for i in range(N)]
s = 0
Score = 0 

for x in range(N):
	for i in range(N):
		if (i+1)%(x+1)==0:
			s += a[i]
	if s < 0:
		for j in range(N):
			if (j+1)%(x+1)==0:
				b[j] = 0
	s = 0

c = [x * y for (x, y) in zip(a, b)]

for i in range(N):
	Score += c[i]

print(Score)

Submission status: Wrong Answer

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

R = sum(A)
B = []

S_max = R
A_max = A

while True: # 最適種を打ち続ける
    M = R
    for i in range(0, N+1):
        if i == 0:
            B = A
        else:
            B = [A[j-1] if (j%i != 0) else 0 for j in range(1, N+1)]
        S = sum(B)
        if S > R: # 見つかった良さげな手（≠最適手）
            i_max = i
            S_max = S
            A_max = B
    R = S_max
    A = A_max
    if M == R:
        break

print(R)

Submission status: Wrong Answer

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

R = 0
B = []

while True: # 最適種を打ち続ける
    M = R
    for i in range(0, N+1):
        if i == 0:
            B = A
        else:
            B = [A[j-1] if (j%i != 0) else 0 for j in range(1, N+1)]
        S = sum(B)
        if S > R:
            R = S
            A = B
    if M == R:
        break

print(R)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

from sys import stdin
from fractions import gcd	# math.gcd is introduced by python 3.5
from functools import reduce

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

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(t + (i,))
  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 solve(a):
  n = len(a)
  for tl in tuples(n, n):
    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))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

from sys import stdin
from fractions import gcd	# math.gcd is introduced by python 3.5

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

def tuple_list(n, m, N, tpl):
  """
  The list of m-tuples over {1,2,...,n}.
  Each element of the m-tuple is not a divisor of another element of the tuple.
  The lcm of any element of the m-tuple and the maximum value in the tuple is
  less than or equal to N.
  :param N: the maximum label
  :param tpl: a partially constructed tuple (in descending order)
  """
  if m <= 0: return [()]

  ls = []
  for i in range(n, 0, -1):
    if len(tpl) > 0:
      if lcm(i, tpl[0]) > N or \
         any(j % i == 0 for j in tpl): continue

    tl = tuple_list(i - 1, m - 1, N, tpl + (i,))
    ls.extend([t + (i,) for t in tl])
  return ls

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 solve(a):
  n = len(a)
  ls = []
  for m in range(1, n + 1):
    tl = tuple_list(n, m, n, ())
    if len(tl) == 0: break
    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))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

from sys import stdin
from fractions import gcd	# math.gcd is introduced by python 3.5

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

def tuple_list(n, m, N, tpl):
  """
  The list of m-tuples over {1,2,...,n}.
  Each element of the m-tuple is not a divisor of another element of the tuple.
  The lcm of any element of the m-tuple and the maximum value in the tuple is
  less than or equal to N.
  :param N: the maximum label
  :param tpl: a partially constructed tuple (in descending order)
  """
  if m <= 0: return [()]

  ls = []
  for i in range(n, 0, -1):
    if len(tpl) > 0:
      if lcm(i, tpl[0]) > N or \
         any(j % i == 0 for j in tpl): continue

    tl = tuple_list(i - 1, m - 1, N, tpl + (i,))
    ls.extend([t + (i,) for t in tl])
  return ls

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 solve(a):
  n = len(a)
  ls = []
  for m in range(1, n):
    tl = tuple_list(n, m, n, ())
    if len(tl) == 0: break
    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))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[0]
a.extend([int(i) for i in input().split()])


while True:
  c = 1
  x = sum([i for i in a if i > 0])
  b = x
  y = 0
  
  if x ==0:
    a = [0]
    break
  else:
    while c <= len(a):
      b0 = [j for i, j in enumerate(a) if i % c == 0]

      if sum(b0) < 0:
        b = sum([i for i in b0 if i > 0])

        if b <= x:
          x = b
          y = c

      c += 1

    if not y:
      break
    else:
      a = [j if i % y !=0 else 0  for i, j in enumerate(a)]

if sum(a) < 0:
  print(0)    
else:
  print(sum(a))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[0]
a.extend([int(i) for i in input().split()])

while 1:
  c = len(a)
  x = sum([i for i in a if i > 0])
  b = x
  y = 0
  
  if x ==0:
    a = [0]
    break
  else:
    while c >0:
      b0 = [j for i, j in enumerate(a) if i % c == 0]

      if sum(b0) < 0:
        b = sum([i for i in b0 if i > 0])

      if b < x:
        x = b
        y = c

      c -= 1

    if not y:
      break
    else:
      a =[j if i % y !=0 else 0  for i, j in enumerate(a)]

if sum(a) < 0:
  print(0)    
else:
  print(sum(a))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[0]
a.extend([int(i) for i in input().split()])

while 1:
  c = 1
  x = sum([i for i in a if i > 0])
  b = x
  y = 0
  
  if x ==0:
    a = [0]
    break
  else:
    while c <= len(a):
      b0 = [j for i, j in enumerate(a) if i % c == 0]

      if sum(b0) < 0:
        b = sum([i for i in b0 if i > 0])

      if b < x:
        x = b
        y = c

      c += 1

    if not y:
      break
    else:
      a =[j if i % y !=0 else 0  for i, j in enumerate(a)]

if sum(a) < 0:
  print(0)    
else:
  print(sum(a))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[0]
a.extend([int(i) for i in input().split()])

while 1:
  c = 1
  x = sum([i for i in a if i > 0])
  b = x
  y = 0
  
  if x ==0:
    a=[0]
    break
  else:
    while c <= len(a):
      b0 = [j for i, j in enumerate(a) if i % c == 0]

      if sum(b0) < 0:
        b = sum([i for i in b0 if i > 0])

      if b < x:
        x = b
        y = c

      c += 1

    if not y:
      break
    else:
      a =[j if i % y !=0 else 0  for i, j in enumerate(a)]
    
    
print(sum(a))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[0]
a.extend([int(i) for i in input().split()])

while 1:
  c = 1
  x = sum([i for i in a if i > 0])
  b = x
  y = 0
  
  while c <= len(a):
    b0 = [j for i, j in enumerate(a) if i % c == 0]
    
    if sum(b0) < 0:
      b = sum([i for i in b0 if i > 0])
    
    if b < x:
      x = b
      y = c

    c += 1
  
  if not y:
    break
  else:
    a =[j if i % y !=0 else 0  for i, j in enumerate(a)]
    
    
print(sum(a))

Submission status: Wrong Answer

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

#print(a)

for i in range(N, 0, -1):
#    print(i, a[i])
#    print(sum([a[i*j] for j in range(1, N//i + 1)]))
    if a[i] < 0 and sum([a[i*j] for j in range(1, N//i + 1)]) < 0:
        for j in range(1, N//i + 1):
            a[i*j] = 0

#print(a)
print(sum(a))

Submission status: Wrong Answer

Solution code:
import itertools
import copy

# 最大公約数
def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

# 宝石の数
N = int(input())
# 宝石の得点
a = list(map(int, input().split()))

# 宝石の得点に負があるか否か
if min(a) >= 0:
    # 全てを計算して出力
    print(sum(a))
else:
    # 宝石の得点が負であるインデックスを取得
    minus = [i for i,j in enumerate(a) if j<0]
    # 宝石の得点が負であるインデックスの組み合わせ
    combination = []
    for i in range(len(minus)):
        combination.extend(list(itertools.combinations(minus, (i+1))))
    # インデックスの組み合わせを全て計算
    summation = [sum(a)]
    for i in combination:
        # 元のリストは保持
        a_remove = copy.deepcopy(a)
        for index in i:
            # 削除する代わりに0で置換
            for j in range((len(a)+1)//(index+1)):
                a_remove[(index+1)*j-1] = 0
            summation.append(sum(a_remove))
    print(max(summation))

Submission status: Wrong Answer

Solution code:
def MUL(N, ai):
    if max(ai) <= 0:
        return 0
    ai.insert(0, 0)
    dels = []
    ans = sum(ai)
    while True:
        is_find = False
        del_i = 0
        for i in range(1, len(ai)):
            # tmp = [a for j, a in enumerate(ai) if j%i]
            tmp = []
            for j, a in enumerate(ai):
                if j%i:
                    if dels:
                        for d in dels:
                            if j % d:
                                tmp.append(a)
                                break
                    else:
                        tmp.append(a)

            s_tmp = sum(tmp)
            if s_tmp > ans:
                is_find = True
                ans = s_tmp
                del_i = i

        if is_find:
            dels.append(del_i)
        else:
            break

    return ans


if __name__ == '__main__':
    N = int(input())
    ai = list(map(int, input().split()))
    print(MUL(N, ai))

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 res

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 res