Submission #3448225

---

Source Code Expand

#include <bits/stdc++.h>
#define inf 200000000000
using namespace std;
// 0-indexed
struct Dinic {
  struct edge {
    int to;
    long long cap;
    int rev;
  };
  vector<vector<edge>> lst;
  vector<int> completed;
  vector<int> dist;
  Dinic(int n = 1) {
    // if 1-indexed
    //++n;
    lst.resize(n);
    completed.resize(n);
    dist.resize(n);
  }
  bool add(int start, int goal, long long capacity) {
    lst[start].push_back(
        (edge){goal, capacity, (int)lst[goal].size()});
    lst[goal].push_back(
        (edge){start, 0, (int)lst[start].size() - 1});
    return 1;
  }
  // dist = time from start to now number
  void distbfs(int start) {
    fill(dist.begin(), dist.end(), -1);
    queue<int> bfsqu;
    dist[start] = 0;
    bfsqu.push(start);
    while(bfsqu.size() > 0) {
      int now = bfsqu.front();
      bfsqu.pop();
      for(int i = 0; i < lst[now].size(); ++i) {
        edge* nowe = &lst[now][i];
        if(nowe->cap > 0 && dist[nowe->to] < 0) {
          dist[nowe->to] = dist[now] + 1;
          bfsqu.push(nowe->to);
        }
      }
    }
  }
  long long pathdfs(int now, int goal, long long nf) {
    if(now == goal) return nf;
    for(int& i = completed[now]; i < lst[now].size(); ++i) {
      edge* e = &lst[now][i];
      if(e->cap > 0 && dist[now] < dist[e->to]) {
        long long ans =
            pathdfs(e->to, goal, min(nf, e->cap));
        if(ans > 0) {
          e->cap -= ans;
          lst[e->to][e->rev].cap += ans;
          return ans;
        }
      }
    }
    return 0;
  }
  long long solve(int start, int goal) {
    long long ans = 0, nf = 0;
    while(1) {
      // bfs
      distbfs(start);
      // cannnot go to goal from start
      if(dist[goal] < 0) return ans;
      // reset
      fill(completed.begin(), completed.end(), 0);
      while((nf = pathdfs(start, goal, inf)) > 0) ans += nf;
    }
    return -1;
  }
};

int n;
long long a[104] = {0};
long long sum = 0;
Dinic dn;

int main() {
  cin >> n;
  dn = Dinic(n + 2);
  for(int i = 0; i < n; ++i) cin >> a[i];
  for(int i = 0; i < n; ++i) {
    sum += max(0LL, a[i]);
    dn.add(0, i + 1, max(0LL, -a[i]));
    dn.add(i + 1, n + 1, max(0LL, a[i]));
    for(int j = 2; j * (i + 1) <= n; ++j)
      dn.add(i + 1, j * (i + 1), inf);
  }
  cout << sum - dn.solve(0, n + 1) << endl;
  return 0;
}

Submission Info

Judge Result