Submission #8825626

---

Source Code Expand

#include <cassert>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
#include <limits>
#include "limits.h"
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " <<"LINE:"<<__LINE__<<"  "<< #i <<":"<< i << std::endl

 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0)) {
    return 0;
  }
 
  long long x = 1;
 
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P = std::pair<ll, ll>;

class Dinic{
  private:

  struct Edge{
    long long to,cap,rev;
    Edge(long long a,long long b,long long c):to(a),cap(b),rev(c){}
  };

  long long MAX_V;
  std::vector<std::vector<Edge>> graph;
  std::vector<long long> level,iter;

  void bfs(long long s){
    level=std::vector<long long>(MAX_V,-1);
    std::queue<long long> que;
    level[s]=0;
    que.push(s);

    while(!que.empty()){
      long long v=que.front();que.pop();
      for(long long i=0;i<graph[v].size();i++){
        const Edge &e = graph[v][i];
        if(e.cap>0&&level[e.to]<0){
          level[e.to]=level[v]+1;
          que.push(e.to);
        }
      }
    }
  }

  long long dfs(long long v,long long t,long long f){
    if(v==t)return f;
    for(long long i=iter[v];i<graph[v].size();i++){
      Edge &e=graph[v][i];
      if(e.cap>0&&level[v]<level[e.to]){
        long long d=dfs(e.to,t,std::min(f,e.cap));
        if(d>0){
          e.cap-=d;
          graph[e.to][e.rev].cap+=d;
          return d;
        }
      }
    }
    return 0;
  }

  public:

  Dinic(long long n):graph(n),level(n),iter(n),MAX_V(n){}

  void add_edge(long long from,long long to,long long cap){
    graph[from].emplace_back(Edge(to,cap,graph[to].size()));
    graph[to].emplace_back(Edge(from,0,graph[from].size()));
  }

  long long max_flow(long long s,long long t){
    long long flow=0;
    while(1){
      bfs(s);
      if(level[t]<0)return flow;

      iter=std::vector<long long>(MAX_V,0);
      long long f;
      while((f=dfs(s,t,LLONG_MAX))>0){
        flow+=f;
      }
    }
  }
};

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  ll n;
  std::cin>>n;

  const long long INF=1e14;

  Dinic flow(n+2);

  ll sum=0;

  rep(i,1,n+1){
    ll a;
    std::cin>>a;
    if(a>=0){
      sum+=a;
      flow.add_edge(i,n+1,a);
    }else{
      flow.add_edge(0,i,-a);
    }
    for(ll j=2*i;j<n+1;j+=i){
      flow.add_edge(i,j,INF);
    }
  }

  std::cout<<sum-flow.max_flow(0,n+1)<<"\n";

  return 0;
}

Submission Info

Judge Result