Submission #4025957
Source Code Expand
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;
template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;
template<class T>
class Dinic {
struct edge {
int to{}, rev{};
T cap;
edge() = default;
edge(int to, T cap, int rev):to(to), cap(cap), rev(rev) {}
};
int n{};
vector<vector<edge>> G;
vector<int> level, iter;
public:
Dinic() = default;
explicit Dinic(int sz): n(sz), G(n), level(n), iter(n){}
void add_edge(int from, int to, T cap){
G[from].emplace_back(to, cap, G[to].size());
G[to].emplace_back(from, 0, G[from].size()-1);
}
void bfs(int s){
fill(level.begin(), level.end(), -1);
queue<int> Q;
level[s] = 0;
Q.emplace(s);
while(!Q.empty()){
int v = Q.front(); Q.pop();
for (auto &&e : G[v]) {
if(e.cap > 0 && level[e.to] < 0){
level[e.to] = level[v]+1;
Q.emplace(e.to);
}
}
}
}
T dfs(int v, int t, T 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]){
T 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;
}
T flow(int s, int t, T lim = INF<T>){
T fl = 0;
while(true){
bfs(s);
if(level[t] < 0 || lim == 0) return fl;
fill(iter.begin(), iter.end(), 0);
T f;
while((f=dfs(s,t, lim))>0){
fl += f;
lim -= f;
}
}
}
bool back_edge(int s, int t, int from, int to){
for (auto &&e : G[from]) {
if(e.to == to) {
if(e.cap == 0 && flow(from, to, 1) == 0){
flow(from, s, 1);
flow(t, to, 1);
return true;
}
}
}
return false;
}
};
int main() {
int n;
cin >> n;
vector<ll> v(n);
for (auto &&i : v) scanf("%lld", &i);
Dinic<ll> fl(n+2);
ll ans = 0;
for (int i = 0; i < n; ++i) {
if(v[i] >= 0){
fl.add_edge(0, i+1, 0);
fl.add_edge(i+1, n+1, v[i]);
ans += v[i];
}else {
fl.add_edge(0, i+1, -v[i]);
fl.add_edge(i+1, n+1, 0);
}
}
for (int i = 0; i < n; ++i) {
if(v[i] == 0) continue;
for (int j = 0; j < n; ++j) {
if(i == j) continue;
if((j+1)%(i+1) == 0) {
fl.add_edge(i+1, j+1, 1000LL*MOD);
}
}
}
cout << ans-fl.flow(0, n+1) << "\n";
return 0;
}
Submission Info
Submission Time
2019-01-16 20:54:23+0900
Task
E - MUL
User
firiexp
Language
C++14 (GCC 5.4.1)
Score
700
Code Size
3264 Byte
Status
AC
Exec Time
1 ms
Memory
256 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:103:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (auto &&i : v) scanf("%lld", &i);
^
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