Submission #3429773
Source Code Expand
#include<bits/stdc++.h> using namespace std; const int N = 206; typedef long long ll; const ll C = 1e12, inf = 1e18; struct { struct edge { int v; ll r,f; }; vector<edge> e; vector<int> g[N]; int n,s,t, d[N], pr[N]; bitset<N> inq; void init(int _n,int _s,int _t) { n=_n,s=_s,t=_t; } void addE(int u,int v,ll c) { g[u].push_back(e.size()); e.push_back(edge{v,c,0}); g[v].push_back(e.size()); e.push_back(edge{u,0,0}); } ll aug() { fill_n(pr,n,-1); fill_n(d,n,N); d[s] = 0; queue<int> q; inq.reset(); q.push(s); while (q.size()) { int u = q.front(); q.pop(); inq[u] = false; for (int i : g[u]) { if (e[i].r) { int w = d[u] + 1; if (w < d[e[i].v]) { d[e[i].v] = w; pr[e[i].v] = i; if (!inq[e[i].v]) { q.push(e[i].v); inq[e[i].v] = true; } } } } } ll f=inf; for (int u = t; pr[u] != -1; u = e[pr[u]^1].v) f = min(f, e[pr[u]].r); for (int u = t; pr[u] != -1; u = e[pr[u]^1].v) { e[pr[u]].r -= f; e[pr[u]].f += f; e[pr[u]^1].r += f; e[pr[u]^1].f -= f; } return f; } } f; int n,a[N]; int main() { cin >> n; f.init(n+2,0,n+1); ll ans = 0; for (int i = 1; i <= n; ++i) { cin >> a[i]; if (a[i] > 0) { ans += a[i]; f.addE(i,f.t,a[i]); } else { f.addE(f.s,i,-a[i]); } for (int j = i * 2; j <= n; j += i) f.addE(i,j,inf); } ll w; while ((w = f.aug()) != inf) ans -= w; cout << ans << '\n'; }
Submission Info
Submission Time | |
---|---|
Task | E - MUL |
User | pr3pony |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 2083 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 KB |
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 |