Submission #2123075
Source Code Expand
// 基本テンプレート
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
typedef pair<int, int> pii;
typedef long long ll;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
template <typename T>
struct Edge {
int to; T cap, cost; int rev;
Edge(int t, T c, int r) : to(t), cap(c), rev(r) {}
Edge(int t, T ca, T co, int r) : to(t), cap(ca), cost(co), rev(r) {}
};
template <typename T>
using Graph = vector< vector< Edge<T> > >;
template <typename T>
struct Flow {
vector< vector< Edge<T> > > G;
const T MAXC = 1 << 30;
int n;
vector<bool> used;
vector<int> prevv, preve, dist;
Flow(int _n) : G(_n), n(_n), used(_n, false),
prevv(n), preve(n), dist(n, MAXC) {}
// G[e.to][e.rev] で逆辺を操作できる
void add_edge(int from, int to, T cap) {
G[from].push_back(Edge<T>(to, cap, G[to].size()));
G[to].push_back(Edge<T>(from, 0, G[from].size() - 1));
}
void add_edge(int from, int to, T cap, T cost) {
G[from].push_back(Edge<T>(to, cap, cost, G[to].size()));
G[to].push_back(Edge<T>(from, 0, -cost, G[from].size() - 1));
}
T dfs(int v, int t, T f) {
if(v == t) return f;
used[v] = true;
for(int i=0; i < G[v].size(); i++) {
Edge<T> &e = G[v][i];
if(!used[e.to] && e.cap > 0) {
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 max_flow(int s, int t) {
T flow = 0;
while(1) {
fill(used.begin(), used.end(), false);
T f = dfs(s, t, INF);
if(f == 0) return flow;
flow += f;
}
}
T mincost_flow(int s, int t, T f) {
T res = 0;
T ma = MAXC;
while(f > 0) {
fill(dist.begin(), dist.end(), ma);
dist[s] = 0;
bool update = true;
while(update) {
update = false;
for(int v = 0; v < n; v++) {
if(dist[v] == ma) continue;
for(int i=0; i<G[v].size(); i++) {
Edge<T> &e = G[v][i];
if(e.cap>0 && dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}
}
if(dist[t] == ma) return -1;
T d = f;
for(int v = t; v != s; v = prevv[v]) {
d = min(d, G[prevv[v]][preve[v]].cap);
}
f -= d;
res += d * dist[t];
for(int v = t; v != s; v = prevv[v]) {
Edge<T> &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
return res;
}
};
signed main() {
int N; cin >> N;
Flow<int> fl(N+2);
int source = N, sink = source + 1, sum = 0;
vector<int> A(N);
rep(i,0,N) {
cin >> A[i];
if(A[i] > 0) {
sum += A[i];
fl.add_edge(i, sink, A[i]);
}
else {
fl.add_edge(source, i, -A[i]);
}
}
rep(i,0,N) {
int d = i+1;
for(int k=i+d; k<N; k+=d) {
fl.add_edge(i, k, INF);
}
}
cout << sum - fl.max_flow(source, sink) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - MUL |
User |
tsutaj |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
4684 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 |