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:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int, read().split())
a.insert(0,0)

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

print(sum(a))

Submission status: Wrong Answer

Solution code:
s=0
N=int(input())
a=list(map(int,input().split()))
L=list(range(N))
L=list(reversed(L))
for i in L:
  c=i+1
  k=N//c
  for j in range(1,k+1):
    s+=a[c*j-1]
  if s<0:
    for j in range(1,k+1):
      a[c*j-1]=0
  s=0
print(sum(a))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra
import numpy as np
n=int(input())
a=[0]+[int(j)for j in input().split()]
graph=np.zeros((n+2,n+2),dtype=np.int64)
start,goal=0,n+1
for i,j in enumerate(a[1:],1):
    if j>=0:
        graph[start,i]=j
    else:
        graph[i,goal]=-j
for i in range(1,n+1):
    for j in range(2*i,n+1,i):
        graph[j,i]=10**5
def max_flow(graph):
    flow=0
    while True:
        dist,pred=dijkstra(graph,indices=start,return_predecessors=True,unweighted=True)
        if dist[goal]==np.inf:
            return flow
        path=[]
        v=goal
        while True:
            path.append((pred[v],v))
            v=pred[v]
            if v==start:
                break
        add_flow=min(graph[x][y] for x,y in path)
        for x,y in path:
            graph[x][y]-=add_flow
            graph[y][x]+=add_flow
        flow+=add_flow
print(sum(i for i in a if i>0)-max_flow(graph))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0]+list(map(int,input().split()))
prime = [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]
graph = [[] for i in range(n+1)]
def judge(x):
  if sum(a[x:n+1:x]) < 0:
    for j in range(x,n+1,x):
      a[j] = 0
  else:
    a[n//x*x] = sum(a[x:n+1:x])
    for j in range(x,n+1-x,x):
      a[j] = 0
for i in range(1,n+1):
  for x in prime:
    if i%x == 0:
      graph[i].append(i//x)
for i in range(n,0,-1):
  judge(i)
  for j in graph[i]:
    judge(j)
  
print(sum(a))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0]+list(map(int,input().split()))
dvs = [[] for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,i+1):
    if i%j == 0:
      dvs[i].append(j)
def judge(x):
  if sum(a[x:n+1:x]) < 0:
    for j in range(x,n+1,x):
      a[j] = 0
    for j in range(x,n+1,x):
      for y in dvs[j]:
        if x<y and y%x:
          judge(y)
for i in range(n,0,-1):
  judge(i)
print(sum(a))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0]+list(map(int,input().split()))
dvs = [[] for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,i+1):
    if i%j == 0:
      dvs[i].append(j)
def judge(x):
  if sum(a[x:n+1:x]) < 0:
    for j in range(x,n+1,x):
      a[j] = 0
      for y in dvs[j]:
        if x<y and y%x:
          judge(y)
for i in range(n,0,-1):
  judge(i)
print(sum(a))

Submission status: Wrong Answer

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

for i in reversed(range(1,N+1)):
  asum=0
  for j in range(i,N+1,i):
    asum+=alist[j]
    
  if asum<0:
    for j in range(i,N+1,i):
      alist[j]=0
      
#print(alist)
print(sum(alist))

Submission status: Wrong Answer

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


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

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

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

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

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

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

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

print(score - dinic.max_flow())

Submission status: Wrong Answer

Solution code:

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

これ、貪欲で解けるのでは？
負のみ見ていけばよい

負のうち絶対値が大きい方から見ていく。
それを取り除くと決めたとする。
その時,xとしてはその数字を選ぶべき(正を無駄に取り除かないため)
取り除いた時、数が増えるのならxを選択してremove

次に絶対値が小さい数に移る
で解けないか？

いや誤読してて草
結局は右から見ていけばいいんちゃう？
ん～？簡単すぎんか？？？？
制約小さいしだめなケース有りそうで怖い…
ダメ元で提出してみるか？？
"""

N = int(input())

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

use = [True] * N

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

    ns = 0
    for j in range(i,N,i+1):
        if use[j]:
            ns += a[j]

    if ns < 0:
        for j in range(i,N,i+1):
            use[j] = False

ans = 0
for i in range(N):
    if use[i]:
        ans += a[i]
print (ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
a0 = list(map(int, input().split()))

for i in range(N, 0, -1):
    if a0[i - 1] < 0:
        tmp = 0
        b = []
        for j in range(1, 101):
            if i * j - 1 >= N:
                break
            tmp += a0[i * j - 1]
            b.append(i * j - 1)
        if tmp < 0:
            for j in b:
                a0[j] = 0

for k1 in range(N, 0, -1):
    for k2 in range(k1-1, 0, -1):
        a = deepcopy(a0)
        for j in range(1, 101):
            if k1*j-1 >= N:
                break
            a[k1*j-1] = 0
        for j in range(1, 101):
            if k2*j-1 >= N:
                break
            a[k2*j-1] = 0
        for i in range(N, 0, -1):
            if a[i - 1] < 0:
                tmp = 0
                b = []
                for j in range(1, 101):
                    if i * j - 1 >= N:
                        break
                    tmp += a[i * j - 1]
                    b.append(i * j - 1)
                if tmp < 0:
                    for j in b:
                        a[j] = 0
        if sum(a) > sum(a0):
            a0 = a

print(sum(a0))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
a0 = list(map(int, input().split()))

for k1 in range(N, 0, -1):
    for k2 in range(k1-1, 0, -1):
        a = deepcopy(a0)
        for j in range(1, 101):
            if k1*j-1 >= N:
                break
            a[k1*j-1] = 0
        for j in range(1, 101):
            if k2*j-1 >= N:
                break
            a[k2*j-1] = 0
        for i in range(N, 0, -1):
            if a[i - 1] < 0:
                tmp = 0
                b = []
                for j in range(1, 101):
                    if i * j - 1 >= N:
                        break
                    tmp += a[i * j - 1]
                    b.append(i * j - 1)
                if tmp < 0:
                    for j in b:
                        a[j] = 0
        if sum(a) > sum(a0):
            a0 = a

print(sum(a0))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
a0 = list(map(int, input().split()))

for k in range(N, 0, -1):
    a = deepcopy(a0)
    for j in range(1, 101):
        if k*j-1 >= N:
            break
        a[k*j-1] = 0
    for i in range(N, 0, -1):
        if a[i - 1] < 0:
            tmp = 0
            b = []
            for j in range(1, 101):
                if i * j - 1 >= N:
                    break
                tmp += a[i * j - 1]
                b.append(i * j - 1)
            if tmp < 0:
                for j in b:
                    a[j] = 0
    if sum(a) > sum(a0):
        a0 = a

print(sum(a0))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
a0 = list(map(int, input().split()))

for k in range(N-1, -1, -1):
    a = deepcopy(a0)
    a[k] = -10**11
    for i in range(N, 0, -1):
        if a[i - 1] < 0:
            tmp = 0
            b = []
            for j in range(1, 101):
                if i * j - 1 >= N:
                    break
                tmp += a[i * j - 1]
                b.append(i * j - 1)
            if tmp < 0:
                for j in b:
                    a[j] = 0
    if sum(a) > sum(a0):
        a0 = a

print(sum(a0))

Submission status: Wrong Answer

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

for t in range(100):
    for i in range(N, 0, -1):
        if a[i - 1] < 0:
            tmp = 0
            b = []
            for j in range(1, 101):
                if i * j - 1 >= N:
                    break
                tmp += a[i * j - 1]
                b.append(i * j - 1)
            if tmp < 0:
                for j in b:
                    a[j] = 0

print(sum(a))

Submission status: Wrong Answer

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

for t in range(5):
    for i in range(N, 0, -1):
        if a[i - 1] < 0:
            tmp = 0
            b = []
            for j in range(1, 101):
                if i * j - 1 >= N:
                    break
                tmp += a[i * j - 1]
                b.append(i * j - 1)
            if tmp < 0:
                for j in b:
                    a[j] = 0

print(sum(a))

Submission status: Wrong Answer

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

for i in range(N, -1, -1):
    if a[i-1] < 0:
        tmp = 0
        b = []
        for j in range(1, 101):
            if i*j-1 >= N:
                break
            tmp += a[i*j-1]
            b.append(i*j-1)
        if tmp < 0:
            for j in b:
                a[j] = 0
print(sum(a))

Submission status: Wrong Answer

Solution code:
#上から貪欲？

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

brk = [0 for i in range(n+1)]


for i in range(n,0,-1):
    #print(brk)
    tmp = 0
    for j in range((n+i-1)//i + 1):
        if i*j<=n:
            if not brk[i*j]:
                tmp += a[i*j]
    if tmp <= 0:###
        for j in range((n+i-1)//i + 1):
            if i*j<=n:
                brk[i*j] = 1

ans = 0

for i in range(n+1):
    if not brk[i]:
        ans += a[i]
#print(brk)
print(ans)

Submission status: Wrong Answer

Solution code:
#上から貪欲？

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

brk = [0 for i in range(n+1)]


for i in range(n,0,-1):
    #print(brk)
    tmp = 0
    for j in range((n+i-1)//i + 1):
        if i*j<=n:
            if not brk[i*j]:
                tmp += a[i*j]
    if tmp < 0:
        for j in range((n+i-1)//i + 1):
            if i*j<=n:
                brk[i*j] = 1

ans = 0

for i in range(n+1):
    if not brk[i]:
        ans += a[i]
#print(brk)
print(ans)

Submission status: Wrong Answer

Solution code:
#上から貪欲？

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

brk = [0 for i in range(n+1)]


for i in range(n,0,-1):
    print(brk)
    tmp = 0
    for j in range((n+i-1)//i + 1):
        if i*j<=n:
            if not brk[i*j]:
                tmp += a[i*j]
    if tmp < 0:
        for j in range((n+i-1)//i + 1):
            if i*j<=n:
                brk[i*j] = 1

ans = 0

for i in range(n+1):
    if not brk[i]:
        ans += a[i]
#print(brk)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
t = [0] * (N + 1)
for i in range(1, N + 1):
  for j in range(i - 1, N, i):
    t[i] -= a[j]
#print(t)
x = 0
res = sum(a)
vis = set()
for _ in range(N):
  ts = t + []
  if x > 0:
    for i in range(x, N + 1, x):
      vis.add(i)
    for i in range(1, N + 1):
      if i in vis:
        for j in range(1, N + 1):
          if i % j == 0:
            ts[j] += a[i - 1]
  #print(ts, x, vis)
  r = 0
  rx = 0
  for i in range(N + 1):
    if r < ts[i]:
      r = ts[i]
      rx = i
  x = rx
  if x == 0: break
for y in vis:
  res -= a[y - 1]
print(res)

Submission status: Wrong Answer

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(2,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: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return

#B
def B():

    return

#C
def C():
    n = I()
    a = LI()
    f = [1]*n
    for i in range(n)[::-1]:
        x = i+1
        j = i
        s = 0
        while j < n:
            s += a[j]*f[j]
            j += x
        if s <= 0:
            j = i
            while j < n:
                f[j] = 0
                j += x
    ans = 0
    for i in range(n):
        ans += a[i]*f[i]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return

#B
def B():

    return

#C
def C():
    n = I()
    a = LI()
    f = [1]*n
    for i in range(n)[::-1]:
        x = i+1
        j = i
        s = 0
        while j < n:
            s += f[j]*a[j]
            j += x
        if s < 0:
            j = i
            while j < n:
                f[j] = 0
                j += x
    ans = 0
    for i in range(n):
        ans += a[i]*f[i]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return

#B
def B():

    return

#C
def C():
    n = I()
    a = LI()
    f = [1]*n
    for i in range(n-1)[::-1]:
        x = i+1
        j = i
        s = 0
        while j < n:
            s += f[j]*a[j]
            j += x
        if s < 0:
            j = i
            while j < n:
                f[j] = 0
                j += x
    ans = 0
    for i in range(n):
        ans += a[i]*f[i]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def edmonds_karp(s, t, C):
    import copy
    import collections

    r = copy.deepcopy(c)
    maxf = 0

    while True:
        q, found = collections.deque(), False
        q.append(([S], 10 ** 15))
        while len(q) > 0:
            p, minf = q.popleft()
            for to, flow in r[p[-1]].items():
                if flow == 0:
                    continue
                elif to == T:
                    p, minf = p + [to], min(flow, minf)
                    found = True
                    break
                elif not to in p:
                    q.append((p + [to], min(flow, minf)))

        if not found:
            break

        for i in range(len(p) - 1):
            r[p[i]][p[i + 1]] -= minf
            if p[i] in r[p[i + 1]]:
                r[p[i + 1]][p[i]] += minf
            else:
                r[p[i + 1]][p[i]] = minf
        maxf += minf

    return maxf


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

gain = sum([max(a, 0) for a in A])

# Flow network
S, T = 0, N + 1
c = [{} for i in range(N + 2)]
for i in range(N):
    ix = i + 1
    if A[i] <= 0:
        c[S][ix] = -A[i]
    else:
        c[ix][T] = A[i]

    for j in range(2 * ix, N + 1, ix):
        c[ix][j] = 10 ** 15

print(gain - edmonds_karp(S, T, c))

Submission status: Wrong Answer

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

erased = [False]*(n)

for i in reversed(range(n)):
    sum_num = 0
    add_j = i
    j = i
    while j < n:
        if not erased[j]:
            sum_num += a[j]
        j += add_j
    if i == 1:
        print(max(sum_num, 0))
        exit()
    if sum_num < 0:
        j = i
        while j < n:
            erased[j] = True
            j += add_j

Submission status: Wrong Answer

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

erased = [False]*(n)

for i in reversed(range(n)):
    if i == 0:
        break
    sum_num = 0
    add_j = i
    j = i
    while j < n:
        if not erased[j]:
            sum_num += a[j]
        j += add_j
    if sum_num < 0:
        j = i
        while j < n:
            erased[j] = True
            j += add_j
ans = 0
for i in range(n):
    if not erased[i]:
        ans += a[i]
print(ans)

Submission status: Wrong Answer

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

erased = [False]*(n+1)

for i in reversed(range(n)):
    if i == 0:
        break
    sum_num = 0
    add_j = i
    j = i
    while j < n:
        if not erased[j]:
            sum_num += a[j]
        j += add_j
    if sum_num < 0:
        j = i
        while j < n:
            erased[j] = True
            j += add_j
ans = 0
for i in range(n):
    if not erased[i]:
        ans += a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
def mulsum(N, A, x, broken):
    ret = 0
    for i in range(x, N, x+1):
        if i not in broken:
            ret += A[i]
    return ret


def main():
    N = int(input())
    A = list(map(int, input().split()))
    broken = set()
    for i in range(N)[::-1]:
        s = mulsum(N, A, i, broken)
        if s < 0:
            for j in range(i, N, i+1):
                broken.add(j)
    print(mulsum(N, A, 0, broken))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
flag = 1
for i in a:
    if i > 0:
        flag = 0
if flag:
    print(0)
else:
    flag_ = 1
    while flag_:
        ans = sum(a)
        prime = [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]
        b = [[] for i in range(100)]
        for i in prime:
            j = i
            while j <= n:
                b[i].append(a[j - 1])
                j += i
        c = []
        flag_ = 0
        for i in b:
            if sum(i) < 0:
                flag_ = 1
            c.append(sum(i))
        dis = 0
        mi = 0
        for i in range(100):
            if c[i] < mi:
                mi = c[i]
                dis = i
        if mi >= 0:
            break
        for i in range(1, n + 1):
            if i % dis == 0:
                a[i - 1] = 0
        ans += -mi
    print(ans)

Submission status: Wrong Answer

Solution code:
class maxFlow:
  def __init__(self, num):
    self.Len = num
    self.L = [[0] * num for i in range(num)]

  def setL(self, a, b, x):
    self.L[a][b] = x

  def getL(self, a, b):
    return self.L[a][b]

  def setLR(self, a, b, x):
    self.setL(a, b, x)
    self.setL(b, a, x)

  def setS(self, s, X, Y):
    for i in range(len(X)):
      self.setL(s, X[i], Y[i])

  def setSn(self, s, X, n):
    Y = [n for i in range(len(X))]
    self.setS(s, X, Y)

  def setT(self, t, X, Y):
    for i in range(len(X)):
      self.setL(X[i], t, Y[i])

  def setTn(self, t, X, n):
    Y = [n for i in range(len(X))]
    self.setT(t, X, Y)

  def getAns(self, t):
    return sum(self.L[t])

  def DFS(self, s, t):
    S = [[s, 0]]
    P = [0] * self.Len
    D = [0] * self.Len
    while S != []:
      k = S.pop()
      P[k[1]] = k[0]
      if self.L[k[0]][self.Len - 1] > 0:
        P[k[1] + 1] = self.Len - 1
        return P
      for i in range(self.Len):
        if D[i] == 0 and self.L[k[0]][i] > 0:
          S.append([i, k[1] + 1])
          D[i] = 1
    return False

  def exe(self):
    while True:
      P = self.DFS(0, self.Len - 1)
      if P == False:
        break
      mi = self.L[P[0]][P[1]]
      Last = self.Len
      for i in range(2, Last):
        if P[i - 1] == self.Len - 1:
          Last = i
          break
        t = self.L[P[i - 1]][P[i]]
        if t < mi:
          mi = t
      for i in range(1, Last):
        self.L[P[i - 1]][P[i]] -= mi
        self.L[P[i]][P[i - 1]] += mi

N = int(input())
a = list(map(int, input().split()))
m = maxFlow(N + 2)
  
for i in range(1, N + 1):
  cnt = 0
  for j in range(i, N + 1, i):
    cnt -= a[j - 1]
    if cnt > 0:
      m.setL(j - i, j, max(cnt, m.getL(j - i, j)))
  if cnt > 0:
    m.setL(j, -1, max(cnt, m.getL(j, -1)))

m.exe()
print(m.getAns(-1) + sum(a))

Submission status: Wrong Answer

Solution code:
class maxFlow:
  def __init__(self, num):
    self.Len = num
    self.L = [[0] * num for i in range(num)]

  def setL(self, a, b, x):
    self.L[a][b] = x

  def getL(self, a, b):
    return self.L[a][b]

  def setLR(self, a, b, x):
    self.setL(a, b, x)
    self.setL(b, a, x)

  def setS(self, s, X, Y):
    for i in range(len(X)):
      self.setL(s, X[i], Y[i])

  def setSn(self, s, X, n):
    Y = [n for i in range(len(X))]
    self.setS(s, X, Y)

  def setT(self, t, X, Y):
    for i in range(len(X)):
      self.setL(X[i], t, Y[i])

  def setTn(self, t, X, n):
    Y = [n for i in range(len(X))]
    self.setT(t, X, Y)

  def getAns(self, t):
    return sum(self.L[t])

  def DFS(self, s, t):
    S = [[s, 0]]
    P = [0] * self.Len
    D = [0] * self.Len
    while S != []:
      k = S.pop()
      P[k[1]] = k[0]
      if self.L[k[0]][self.Len - 1] > 0:
        P[k[1] + 1] = self.Len - 1
        return P
      for i in range(self.Len):
        if D[i] == 0 and self.L[k[0]][i] > 0:
          S.append([i, k[1] + 1])
          D[i] = 1
    return False

  def exe(self):
    while True:
      P = self.DFS(0, self.Len - 1)
      if P == False:
        break
      mi = self.L[P[0]][P[1]]
      Last = self.Len
      for i in range(2, Last):
        if P[i - 1] == self.Len - 1:
          Last = i
          break
        t = self.L[P[i - 1]][P[i]]
        if t < mi:
          mi = t
      for i in range(1, Last):
        self.L[P[i - 1]][P[i]] -= mi
        self.L[P[i]][P[i - 1]] += mi

N = int(input())
a = list(map(int, input().split()))
m = maxFlow(N + 2)
  
for i in range(1, N + 1):
  cnt = 0
  for j in range(i, N + 1, i):
    cnt -= a[j - 1]
    if cnt > 0:
      m.setL(j - i, j, max(cnt, m.getL(j - i, j)))
    else:
      m.setL(j, j - i, max(-cnt, m.getL(j, j - i)))
  if cnt > 0:
    m.setL(j, -1, max(cnt, m.getL(j, -1)))

m.exe()
print(m.getAns(-1) + sum(a))

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