Submission #3450739

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 105;
int N;
int A[MAX_N];

class Dinic{
public:
  Dinic(int v) : MAX_V(v) {
    init();
    G.resize(v);
    level.resize(v);
    iter.resize(v);
  }

  void init() {
    G.clear(); level.clear(); iter.clear();
  }

  void addEdge(LL from, LL to, LL cap) {
    G[from].push_back(edge(to, cap, G[to].size()));
    G[to].push_back(edge(from, 0, G[from].size()-1));
  }

  void bfs(LL s) {
      fill(begin(level), end(level), -1);
      queue<LL> que;
      level[s] = 0;
      que.push(s);
      while(!que.empty()){
          LL v = que.front(); que.pop();
          for(LL 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);
              }
          }
      }
  }

  LL dfs(LL v, LL t, LL f) {
      if(v==t) return f;
      for(LL &i = iter[v]; i < G[v].size(); i++) {
          edge &e = G[v][i];
          if(e.cap > 0 && level[v] < level[e.to]) {
              LL 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;
  }

  LL maxFlow(LL s, LL t)
  {
      LL flow = 0;
      while(true) {
          bfs(s);
          if(level[t] < 0) {
              return flow;
          }
          fill(begin(iter), end(iter), 0);
          LL f;
          while((f = dfs(s, t, INF)) > 0) {
              flow += f;
          }
      }
  }

private:
  int MAX_V;

  struct edge {
      LL to, cap, rev;
      edge(LL to, LL cap, LL rev) : to(to), cap(cap), rev(rev) {}
  };

  vector<vector<edge>> G;
  vector<LL> level;
  vector<LL> iter;
};

signed main()
{
  cin >> N;
  REP(i,N) {
    cin >> A[i];
  }

  int ans = 0;
  Dinic dinic(N+5);
  REP(i,N) {
    if(A[i] >= 0) {
      ans += A[i];
      dinic.addEdge(i,N+1,A[i]);
    } else {
      dinic.addEdge(N,i,-A[i]);
    }
  }

  FOR(i,1,N+1) {
    for(int j = 2; i*j <= N; j++) { 
      dinic.addEdge(i-1,i*j-1,INF_LL);
    }
  }

  cout << ans - dinic.maxFlow(N,N+1) << endl;

  return 0;
}

Submission Info

Judge Result