Submission #5540017

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 107;
const int INF = 1e18 + 7;
const int S = 0, T = N - 1;
int n;
int a[N];
struct Edge {
    int v, c, f;
};  
vector <int> g[N];
vector <Edge> ed;      
void add(int u, int v, int c) {
    #ifdef HOME
    cout << "edge " << u << "->" << v << " : " << c << '\n';
    #endif
    g[u].push_back(ed.size());
    ed.push_back({v, c, 0});
    g[v].push_back(ed.size());
    ed.push_back({u, 0, 0});
}   
bool used[N];
int dfs(int u, int cur) {
    used[u] = 1;
    #ifdef HOME
    cout << "dfs " << u << ' ' << cur << '\n';
    #endif
    if (u == T) return cur;
    for (int i : g[u]) {
        auto &e = ed[i];
        if (!used[e.v] && e.f < e.c) {
            int t = dfs(e.v, min(cur, e.c - e.f));
            if (t) {
                e.f += t;
                ed[i^1].f -= t;
                return t;
            }   
        }   
    }   
    #ifdef HOME
    cout << "out " << u << '\n';
    #endif
    return 0;
}   
int maxflow() {
    int ans = 0;
    while (1) {
        memset(used, 0, sizeof used);
        int t = dfs(S, INF);
        if (t) ans += t;
        else break;
    }   
    return ans;
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        if (a[i] > 0) {
            add(i, T, a[i]);
        }
        else {
            add(S, i, -a[i]);
        }   
    }   
    for (int i = 1; i <= n; ++i) {
        for (int j = i * 2; j <= n; j += i) {
            add(i, j, INF);
        }
    }   
    int best = 0;
    for (int i = 1; i <= n; ++i) best += max(0ll, a[i]);
    cout << best - maxflow() << '\n';
}   

Submission Info

Judge Result