Submission #3476855


Source Code Expand

Copy
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
#define int long long
struct edge{int to, cap, rev;};
vector< vector<edge> > G(102);
int level[100];
int iter[100];
const int INF = 1e15;

void bfs(int s){
  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);
      }
    }
  }
}

int dfs(int v, int t, int f){
  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]){
      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;
}

int max_flow(int s, int t){
  int flow = 0;
  for(;;){
    bfs(s);
    if(level[t] < 0) return flow;
    memset(iter,0,sizeof(iter));
    int f;
    while((f = dfs(s,t,INF)) > 0){
      flow += f;
    }
  }
}

int main(){
  int N;
  cin >> N;
  int ans = 0LL;
  for(int i = 1; i <= N; ++i){
    int a;
    cin >> a;
    if(a > 0){
      ans += a;
      G[i].push_back((edge){N+1,a,G[N+1].size()});
      G[N+1].push_back((edge){i,0,G[i].size()-1});
    }else{
      G[0].push_back((edge){i,-a,G[i].size()});
      G[i].push_back((edge){0,0,G[0].size()-1});
    }
  }
  for(int i = 1; i <= N; ++i){
    for(int j = 2; i*j <= N; ++j){
      G[i].push_back((edge){i*j,INF,G[i*j].size()});
      G[i*j].push_back((edge){i,0,G[i].size()-1});
    }
  }
  cout << ans - max_flow(0,N+1) << endl;
  return 0;
}

Submission Info

Submission Time
Task E - MUL
User TAB
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1821 Byte
Status

Compile Error

./Main.cpp:61:10: error: ‘::main’ must return ‘int’
 int main(){
          ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:70:46: warning: narrowing conversion of ‘(& G.std::vector<_Tp, _Alloc>::operator[]<std::vector<edge>, std::allocator<std::vector<edge> > >(((std::vector<std::vector<edge> >::size_type)(N + 1ll))))->std::vector<_Tp, _Alloc>::size<edge, std::allocator<edge> >()’ from ‘std::vector<edge>::size_type {aka long unsigned int}’ to ‘long long int’ inside { } [-Wnarrowing]
       G[i].push_back((edge){N+1,a,G[N+1].size()});
                                              ^
./Main.cpp:71:46: warning: narrowing conversion of ‘((& G.std::vector<_Tp, _Alloc>::operator[]<std::vector<edge>, std::allocator<std::vector<edge> > >(((std::vector<std::vector<edge> >::size_type)i)))->std::vector<_Tp, _Alloc>::size<edge, std::allocator<edge> >() + 18446744073709551615ul)’ from ‘std::vector<edge>::size_type {aka long unsigned int}’ to ‘long long int’ inside { } [-Wnarrowing]
       G[N+1].push_back((edge){i,0,G...