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 |
|
|
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 |