Submission #2123128
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i<r;i++)
#define dec(i, l, r) for (int i = l; i>=r;i--)
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define pb(c) push_back(c)
#define vii vector<pair<int,int>>
#define ii pair<int,int>
#define mmax(a, b) (((a)<(b))?b:a)
#define min(a, b) ((a>b)?b:a)
#define mp(i, j) make_pair(i,j)
#define ull unsigned long long int
#define ll long long int
#define pie 3.141592653589793238
#define inf ((ll)1e18)
#define eps 1e-14
#define mod ((int)1e9+7)
#define maxlg 18
#define maxn 200002
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)+1)
typedef long long LL;
struct Edge {
int from, to, cap, flow, index;
Edge(int from, int to, int cap, int flow, int index) :
from(from), to(to), cap(cap), flow(flow), index(index) {}
};
struct PushRelabel {
int N;
vector<vector<Edge> > G;
vector<LL> excess;
vector<int> dist, active, count;
queue<int> Q;
PushRelabel(int N) : N(N), G(N), excess(N), dist(N), active(N), count(2*N) {}
void AddEdge(int from, int to, int cap) {
G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
if (from == to) G[from].back().index++;
G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
}
void Enqueue(int v) {
if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); }
}
void Push(Edge &e) {
int amt = int(min(excess[e.from], LL(e.cap - e.flow)));
if (dist[e.from] <= dist[e.to] || amt == 0) return;
e.flow += amt;
G[e.to][e.index].flow -= amt;
excess[e.to] += amt;
excess[e.from] -= amt;
Enqueue(e.to);
}
void Gap(int k) {
for (int v = 0; v < N; v++) {
if (dist[v] < k) continue;
count[dist[v]]--;
dist[v] = max(dist[v], N+1);
count[dist[v]]++;
Enqueue(v);
}
}
void Relabel(int v) {
count[dist[v]]--;
dist[v] = 2*N;
for (int i = 0; i < G[v].size(); i++)
if (G[v][i].cap - G[v][i].flow > 0)
dist[v] = min(dist[v], dist[G[v][i].to] + 1);
count[dist[v]]++;
Enqueue(v);
}
void Discharge(int v) {
for (int i = 0; excess[v] > 0 && i < G[v].size(); i++) Push(G[v][i]);
if (excess[v] > 0) {
if (count[dist[v]] == 1)
Gap(dist[v]);
else
Relabel(v);
}
}
LL GetMaxFlow(int s, int t) {
count[0] = N-1;
count[N] = 1;
dist[s] = N;
active[s] = active[t] = true;
for (int i = 0; i < G[s].size(); i++) {
excess[s] += G[s][i].cap;
Push(G[s][i]);
}
while (!Q.empty()) {
int v = Q.front();
Q.pop();
active[v] = false;
Discharge(v);
}
LL totflow = 0;
for (int i = 0; i < G[s].size(); i++) totflow += G[s][i].flow;
return totflow;
}
};
int id=1;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifndef ONLINE_JUDGE
#endif
int n;
cin>>n;
ll sum=0;
int arr[n];
rep (i,0,n) {
cin>>arr[i];
if (arr[i]>0)
sum+=arr[i];
}
PushRelabel mf(2+n);
int sink = id+n;
rep (i,0,n) {
if (arr[i]<0)
mf.AddEdge(0,i+1,-arr[i]);
else
mf.AddEdge(i+1,n+1,arr[i]);
}
rep (i,1,n+1) {
int mul = 2*i;
while (mul<=n) {
mf.AddEdge(i,mul,(int)1e9);
mul +=i;
}
}
cout<<sum-mf.GetMaxFlow(0,n+1);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - MUL |
User |
arasmus |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
3862 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 |