Submission #2123350
Source Code Expand
#include<iostream> #include<algorithm> #include<vector> #include<climits> using namespace std; typedef long long int ll; static const int MAX_N = 100; static const ll INF = LLONG_MAX; struct edge{int to; ll cap; int rev;}; vector<edge> G[MAX_N + 2]; int N; ll A[MAX_N + 1]; bool used[MAX_N + 2]; void add_edge(int from, int to, ll cap){ G[from].push_back((edge){to, cap, G[to].size()}); G[to].push_back((edge){from, 0, G[from].size() - 1}); } ll dfs(int v, int t, ll 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){ 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 max_flow(int s, int t){ ll flow = 0; for(;;){ fill(used, used + N + 2, false); ll f = dfs(s, t, INF); if(f == 0) return flow; flow += f; } } int main(){ cin >> N; for(int i = 1; i <= N; i++) cin >> A[i]; ll sum = 0LL; 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]); sum += A[i]; } for(int j = 2; j * i <= N; j++){ add_edge(i, j * i, INF); } } cout << sum - max_flow(0, N + 1) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - MUL |
User | utsumi |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1343 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 KB |
Compile Error
./Main.cpp: In function ‘void add_edge(int, int, ll)’: ./Main.cpp:19: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 ‘int’ inside { } [-Wnarrowing] G[from].push_back((edge){to, cap, G[to].size()}); ^ ./Main.cpp:20: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 ‘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 | 1 ms | 256 KB |
small_2 | AC | 1 ms | 256 KB |
small_3 | AC | 1 ms | 256 KB |
small_4 | AC | 1 ms | 256 KB |