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: Runtime Error

Solution code:
#include <stdio.h>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
const int N=1e2+10;
const long long int INF=1e16+10;
const int MAX_V=800;
struct edge
{
    long long int to,cap;
	int rev;//终点、容量、反向边
};
vector<edge>G[MAX_V];//图的邻接表表示
int level[MAX_V];//顶点到源点的距离标号
int iter[MAX_V];//当前弧，在其之前的边都已经没有用了
void add_edge(int from,int to,long long int cap)//向图中增加一条从from到to的容量为cap的边
{
    G[from].push_back((edge){to,cap,(int)G[to].size()});
     G[to].push_back((edge){from,0,(int)G[from].size()-1});
}
void bfs(int s)//通过BFS计算从源点出发的距离标号
{
    memset(level,-1,sizeof(level));
    queue<int>que;
    level[s]=0;
    que.push(s);
    while(!que.empty())
    {
        int v=que.front();
        que.pop();
        for(int i=0; i<G[v].size(); ++i)
        {
            edge &e=G[v][i];
            if(e.cap>0&&level[e.to]<0)
            {
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}
long long int dfs(int v,int t,long long int f)//DFS寻找增广路
{
    if(v==t) return f;
    for(int &i=iter[v]; i<G[v].size(); ++i)
    {
        edge &e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to])
        {
            long long int d=dfs(e.to,t,min(f,e.cap));
            if(d>0)
            {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
long long int Dinic(int s,int t)//求解s到t的最大流
{
    long long int maxflow=0;
    while(1)
    {
        bfs(s);
        if(level[t]<0) return maxflow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dfs(s,t,INF))>0)
            maxflow+=f;
    }
}
int main(){
	int n,s=N-1,t=N-2;
	long long int temp,tot=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&temp);
		if(temp>0)add_edge(i,t,temp);
		else add_edge(s,i,-temp);
		for(int j=i<<1;j<=n;j+=i)add_edge(i,j,INF);
		if(temp>0)tot+=temp;
	}
	printf("%lld\n",tot-Dinic(s,t));
}

Submission status: Runtime Error

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)

for x in range(34, 51):
    if As[x - 1] + As[x * 2 - 1] < 0:
        As[x - 1] = 0
        As[x * 2 - 1] = 0

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

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

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

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

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

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

print(max(memo.values()))

Submission status: Runtime Error

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:
        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: Runtime Error

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)
ccc=0
import random
for _ in range(100):
    c=check(random.shuffle(aa[i]), broken.copy())
    ccc=max(ccc,c)
print(ans+ccc)

Submission status: Runtime Error

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: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=A[:]
while True:
  B=A[:]
  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: Runtime Error

Solution code:
#include<cstdio>
int main(){
	int n;
	scanf("%d",&n);
	int a[n]={};
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=n-1;i>=0;i--){
		if(a[i]<0){
			int k=0;
			for(int j=i;j<n;j+=i+1){
				k+=a[j];
			}
			if(k<0){
				for(int j=i;j<n;j+=i+1){
					a[j]=0;
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		ans+=a[i];
	}
	printf("%d\n",ans);
	return 0;
}

Submission status: Runtime Error

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(max(0,p[1])