Submission #2124098


Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_V 110
#define INF 10000000000000
#define int long long

struct edge { int to, cap, rev; };

vector<edge> G[MAX_V];
bool used[MAX_V];

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

int dfs(int v, int t, int f) {
  if (v == t) return f;
  used[v] = true;
  for (int i = 0; i < G[v].size(); i++) {
    edge &e = G[v][i];
    if (!used[e.to] && e.cap > 0) {
      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 ( ; ; ) {
    fill(used, used + MAX_V, false);
    int f = dfs(s, t, INF);
    if (f == 0) return flow;
    flow += f;
  }
}

signed main() {
  int n;
  cin >> n;
  int a[n + 1];
  for (int i = 1; i < n + 1; i++) {
    cin >> a[i];
  }
  int pos_sum = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] > 0) pos_sum += a[i];
  }
  for (int i = 1; i <= n; i++) {
    if (a[i] <= 0) add_edge(0, i, -a[i]);
    else add_edge(i, n + 1, a[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i + i; j <= n; j += i) {
      add_edge(i, j, INF);
    }
  }
  cout << pos_sum - max_flow(0, n + 1) << endl;
  return 0;
}

Submission Info

Submission Time
Task E - MUL
User madman6
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1454 Byte
Status AC
Exec Time 2 ms
Memory 384 KB

Compile Error

./Main.cpp: In function ‘void add_edge(long long int, long long int, long long int)’:
./Main.cpp:15:47: warning: narrowing conversion of ‘G[to].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[from].push_back((edge){to, cap, G[to].size()});
                                               ^
./Main.cpp:16:50: warning: narrowing conversion of ‘(G[from].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[to].push_back((edge){from, 0, G[from].size() - 1});
                                                  ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 4
AC × 49
Set Name Test Cases
Sample example_0, example_1, example_2, example_3
All example_0, example_1, example_2, example_3, kimeuti_0, kimeuti_1, kimeuti_10, kimeuti_11, kimeuti_12, kimeuti_13, kimeuti_14, kimeuti_15, kimeuti_16, kimeuti_17, kimeuti_18, kimeuti_19, kimeuti_2, kimeuti_3, kimeuti_4, kimeuti_5, kimeuti_6, kimeuti_7, kimeuti_8, kimeuti_9, rand_0, rand_1, rand_10, rand_11, rand_12, rand_13, rand_14, rand_15, rand_16, rand_17, rand_18, rand_19, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, small_0, small_1, small_2, small_3, small_4
Case Name Status Exec Time Memory
example_0 AC 1 ms 256 KB
example_1 AC 1 ms 256 KB
example_2 AC 1 ms 256 KB
example_3 AC 1 ms 256 KB
kimeuti_0 AC 1 ms 256 KB
kimeuti_1 AC 1 ms 256 KB
kimeuti_10 AC 1 ms 256 KB
kimeuti_11 AC 1 ms 256 KB
kimeuti_12 AC 1 ms 256 KB
kimeuti_13 AC 1 ms 256 KB
kimeuti_14 AC 1 ms 256 KB
kimeuti_15 AC 1 ms 256 KB
kimeuti_16 AC 1 ms 256 KB
kimeuti_17 AC 1 ms 256 KB
kimeuti_18 AC 1 ms 256 KB
kimeuti_19 AC 1 ms 256 KB
kimeuti_2 AC 1 ms 256 KB
kimeuti_3 AC 1 ms 256 KB
kimeuti_4 AC 1 ms 256 KB
kimeuti_5 AC 1 ms 256 KB
kimeuti_6 AC 1 ms 256 KB
kimeuti_7 AC 1 ms 256 KB
kimeuti_8 AC 1 ms 256 KB
kimeuti_9 AC 1 ms 256 KB
rand_0 AC 1 ms 256 KB
rand_1 AC 1 ms 256 KB
rand_10 AC 1 ms 256 KB
rand_11 AC 1 ms 256 KB
rand_12 AC 1 ms 256 KB
rand_13 AC 1 ms 256 KB
rand_14 AC 1 ms 256 KB
rand_15 AC 1 ms 256 KB
rand_16 AC 1 ms 256 KB
rand_17 AC 1 ms 256 KB
rand_18 AC 1 ms 256 KB
rand_19 AC 1 ms 256 KB
rand_2 AC 1 ms 256 KB
rand_3 AC 1 ms 256 KB
rand_4 AC 1 ms 256 KB
rand_5 AC 1 ms 256 KB
rand_6 AC 1 ms 256 KB
rand_7 AC 1 ms 256 KB
rand_8 AC 1 ms 256 KB
rand_9 AC 1 ms 256 KB
small_0 AC 1 ms 256 KB
small_1 AC 2 ms 384 KB
small_2 AC 1 ms 256 KB
small_3 AC 1 ms 256 KB
small_4 AC 1 ms 256 KB