-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathE.cpp
86 lines (79 loc) · 2.29 KB
/
E.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
LL a[4],b[4],n;
const int MAXN = 2000+5;
namespace Flow{
struct Edge{
int to,w,nxt;
}e[MAXN<<1];
int head[MAXN],cur[MAXN],cnt=1;
int dep[MAXN];
int S,T,N;
inline void add(int u,int v,int w){
e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
e[++cnt] = (Edge){u,0,head[v]};head[v] = cnt;
}
inline bool bfs(){
FOR(i,0,N) cur[i] = head[i],dep[i] = 0;
std::queue<int> q;q.push(S);dep[S] = 1;
while(!q.empty()){
int v = q.front();q.pop();
for(int i = head[v];i;i = e[i].nxt){
if(e[i].w > 0 && !dep[e[i].to]){
dep[e[i].to] = dep[v] + 1;
if(e[i].to == T) return true;
q.push(e[i].to);
}
}
}
return dep[T];
}
inline int dfs(int v,int flow=1e9){
if(v == T) return flow;
if(!flow) return 0;
int ans = 0;
for(int &i = cur[v];i;i = e[i].nxt){
if(e[i].w > 0 && dep[e[i].to] == dep[v] + 1){
int t = dfs(e[i].to,std::min(flow,e[i].w));
if(t>0){
ans += t;flow -= t;
e[i].w -= t;e[i^1].w += t;
if(!flow) break;
}
}
}
return ans;
}
inline int Dinic(){
int ans = 0,t = 0;
while(bfs()) while((t=dfs(S))) ans += t;
return ans;
}
};
using namespace Flow;
signed main(){
scanf("%lld",&n);
FOR(i,1,3) scanf("%lld",a+i);
FOR(i,1,3) scanf("%lld",b+i);
LL a1 = 0,a2 = 0;
FOR(i,1,3) a2 += std::min(a[i],b[i%3+1]);
N = 8;S = 7;T = 8;
FOR(i,1,3) add(S,i,a[i]),add(i+3,T,b[i]),add(i,i+3,3e9);
add(1,3+3,3e9);add(2,1+3,3e9);add(3,2+3,3e9);
a1 = Dinic();
printf("%lld %lld\n",n-a1,a2);
return 0;
}