Submission #2667983
Source Code Expand
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
/*
<url:https://beta.atcoder.jp/contests/arc085/tasks/arc085_c>
問題文============================================================
=================================================================
解説=============================================================
================================================================
*/
#define MAX_V 110
struct edge {
int to; // 行き先
ll cap; // 容量
int rev; // 逆辺
edge() {}
edge(int to, ll cap, int rev) :to(to), cap(cap), rev(rev) {}
};
vector<edge> G[MAX_V]; // グラフの隣接リスト表現
int level[MAX_V]; // sからの距離
int iter[MAX_V]; // どこまで調べ終わったか
// fromからtoへ向かう容量capの辺をグラフに追加する
void add_edge(int from, int to, ll cap) {
G[from].push_back(edge(to, cap, (int)G[to].size()));
G[to].push_back(edge(from, 0, (int)G[from].size() - 1));
}
// sからの最短距離をBFSで計算する
void bfs(int s){
fill(level,level+MAX_V,-1);
queue<int> q;
level[s] = 0;
q.push(s);
while(!q.empty()){
int v = q.front(); q.pop();
for(int i = 0; i < (int)G[v].size();i++){
edge& e = G[v][i];
if(e.cap > 0 && level[e.to] < 0){
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
// 増加パスをDFSで探す
ll dfs(int v, int t,ll 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]){
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(;;){
bfs(s);
if(level[t] < 0) return flow;
fill(iter,iter+MAX_V,0);
ll f;
while((f = dfs(s,t,LINF)) > 0){
flow += f;
}
}
}
ll solve(){
ll res = 0;
int N; cin >> N;
vector<ll> a(N+1);
for(int i = 1; i<=N;i++) {cin >> a[i];}
res = accumulate(a.begin(),a.end(),0LL,[](const ll Sum,const ll V){ return Sum + max(V,0LL);});
int S = 0,T = N+1;
for(int i = 1; i<= N;i++){
if(a[i] >= 0){
add_edge(S,i,a[i]);
}else{
add_edge(i,T,-a[i]);
}
for(int j = i-1; j >= 1; j--){
if(i%j == 0){
add_edge(i,j,INF);
}
}
}
res -= max_flow(S, T);
return res;
}
int main(void) {
cin.tie(0); ios_base::sync_with_stdio(false);
cout << solve() << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - MUL |
User |
clavis1107 |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
3716 Byte |
Status |
AC |
Exec Time |
8 ms |
Memory |
764 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 |
8 ms |
764 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 |