2017-2018 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2017)
A. Airport Coffee
設$f_i$表示考慮前$i$個咖啡廳，且在$i$處買咖啡的最小時間，通過單調隊列優化轉移。
時間復雜度$O(n)$。
#include<cstdio>
const int N=500010;
typedef long long ll;
const double inf=1e20;
ll L,A,B,T,R,lim0,lim1,a[N];
double f[N],val[N];
double dp0=inf;
int id0;
int pre[N];
int i,j,k;
int h=1,t,q[N];
double ans;
int fin;
int cof[N],cnt,n;
int main(){
scanf("%lld%lld%lld%lld%lld",&L,&A,&B,&T,&R);
lim0=A*T+R*B;
lim1=T*A;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
ans=1.0*L/A;
for(i=j=k=1;i<=n;i++){
f[i]=1.0*a[i]/A;
while(j<i&&a[i]-a[j]>=lim0){
double now=f[j]-1.0*a[j]/A;
if(now<dp0){
dp0=now;
id0=j;
}
j++;
}
if(id0){
double now=dp0+1.0*(a[i]-lim0)/A+T+R;
if(now<f[i]){
f[i]=now;
pre[i]=id0;
}
}
while(k<i&&a[i]-a[k]>=lim1){
val[k]=f[k]-1.0*a[k]/B;
while(h<=t&&val[q[t]]>val[k])t--;
q[++t]=k;
k++;
}
while(h<=t&&a[i]-a[q[h]]>=lim0)h++;
if(h<=t){
double now=val[q[h]]+1.0*(a[i]-lim1)/B+T;
if(now<f[i]){
f[i]=now;
pre[i]=q[h];
}
}
double ret=f[i];
ll d=L-a[i];
if(d<=lim1){
ret+=1.0*d/A;
}else if(d<=lim0){
ret+=1.0*(d-lim1)/B+T;
}else{
ret+=1.0*(d-lim0)/A+T+R;
}
if(ret<ans){
ans=ret;
fin=i;
}
}
while(fin){
cof[++cnt]=fin;
fin=pre[fin];
}
printf("%d\n",cnt);
for(i=cnt;i;i--)printf("%d ",cof[i]-1);
}
//0 .. n-1
B. Best Relay Team
按題意模擬即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define MC(x, y) memcpy(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1010, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int l, r;
struct A
{
string s;
double fi, se;
}a[N], b[N];
int n;
string ss[5];
bool cmp(A a, A b)
{
return a.se < b.se;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++){
cin >> a[i].s;
scanf("%lf%lf", &a[i].fi, &a[i].se);
a[i + n] = a[i];
}
double ans = 1e9;
for(int i = 1; i <= n; i ++){
MC(b, a);
sort(b + i + 1, b + n + i, cmp);
double tmp = b[i].fi + b[i + 1].se + b[i + 2].se + b[i + 3].se;
if(tmp < ans){
ans = tmp;
ss[1] = b[i].s;
ss[2] = b[i + 1].s;
ss[3] = b[i + 2].s;
ss[4] = b[i + 3].s;
}
}
printf("%.2f\n", ans);
for(int i = 1; i <= 4; i ++){
//printf("%s\n", ss[i]);
cout << ss[i] << endl;
}
scanf("%d", &n);
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復雜度&&優化】
*/
C. Compass Card Sales
按題意模擬即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n;
struct A
{
int v[3];
int id;
int val;
}a[N];// keep a not modified
struct B
{
int id;
int val;
bool operator < (const B & b)const
{
if(val != b.val)return val < b.val;
return id > b.id;
}
};
set<int>sot[3][720];
set<B>b;
//use the a[o]
int getval(int o)
{
int val = 0;
for(int i = 0; i < 3; ++i)
{
int pos = a[o].v[i];
if(sot[i][pos].size() >= 2)
{
continue;
}
int pre = pos + 360;
do
{
--pre;
}while(!sot[i][pre].size());
int suf = pos;
do
{
++suf;
}while(!sot[i][suf].size());
val += (pos + 360 - pre) + (suf - pos);
}
//printf("o = %d a[o].id = %d a[o].val = %d\n", o, a[o].id, val);
return val;
}
map<int, int>mop;
int main()
{
while(~scanf("%d",&n))
{
mop.clear();
for(int i = 0; i < 3; ++i)
{
for(int j = 0; j < 720; ++j)
{
sot[i][j].clear();
}
}
b.clear();
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j < 3; ++j)
{
scanf("%d", &a[i].v[j]);
}
scanf("%d", &a[i].id);
mop[a[i].id] = i;
for(int j = 0; j < 3; ++j)
{
int p = a[i].v[j];
int o = a[i].id;
sot[j][p].insert(o);
sot[j][p + 360].insert(o);
}
}
//a index is a input order
for(int i = 1; i <= n; ++i)
{
a[i].val = getval(i);
b.insert({a[i].id, a[i].val});
}
while(n--)
{
int id = b.begin()->id;
int o = mop[id];
printf("%d\n", id);
b.erase({id, a[o].val});
for(int i = 0; i < 3; ++i)
{
int pos = a[o].v[i];
sot[i][pos].erase(id);
sot[i][pos + 360].erase(id);
}
for(int i = 0; i < 3; ++i)
{
int pos = a[o].v[i];
if(sot[i][pos].size() == 1)
{
int rst = mop[*sot[i][pos].begin()];
b.erase({a[rst].id, a[rst].val});
a[rst].val = getval(rst);
b.insert({a[rst].id, a[rst].val});
}
else if(sot[i][pos].size() == 0 && n > 1)
{
int pos = a[o].v[i];
int pre = pos + 360;
do
{
--pre;
}while(!sot[i][pre].size());
if(sot[i][pre].size() == 1)
{
int rst = mop[*sot[i][pre].begin()];
b.erase({a[rst].id, a[rst].val});
a[rst].val = getval(rst);
b.insert({a[rst].id, a[rst].val});
}
int suf = pos;
do
{
++suf;
}while(!sot[i][suf].size());
if(sot[i][suf].size() == 1)
{
int rst = mop[*sot[i][suf].begin()];
b.erase({a[rst].id, a[rst].val});
a[rst].val = getval(rst);
b.insert({a[rst].id, a[rst].val});
}
}
}
}
}
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復雜度&&優化】
*/
D. Distinctive Character
設$f_S$表示到$S$的最大相似度，顯然對于輸入的$n$個串$a_i$，有$f_{a_i}=k$。
對于$f_S=k$，將$S$修改一位，可以得到$f_{S'}=k-1$，BFS求出所有$S$即可。
時間復雜度$O(k2^k)$。
#include<cstdio>
int n,m,i,h,t,f[1<<20],q[2222222],x,y;
char s[100];
inline void ext(int x,int y){if(f[x]<0)f[q[++t]=x]=y;}
int main(){
scanf("%d%d",&n,&m);
for(i=0;i<1<<m;i++)f[i]=-1;
while(n--){
scanf("%s",s);
int t=0;
for(i=0;i<m;i++)t=t*2+s[i]-'0';
f[t]=m;
}
h=1;
for(i=0;i<1<<m;i++)if(~f[i])q[++t]=i;
while(h<=t){
x=q[h++];
y=f[x]-1;
for(i=0;i<m;i++)ext(x^(1<<i),y);
}
for(i=m-1;~i;i--)printf("%d",x>>i&1);
}
E. Emptying the Baltic
令兩點間的邊權為較大的高度，求出最小生成樹，則每個點的實際水位為起點到它路徑上點權的最大值。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=550,M=N*N;
int n,m,i,j,x,y,tot,id[N][N],a[M],f[M];
int ce;
int v[M*2],nxt[M*2],ed,g[M];
long long ans;
struct E{int x,y,z;E(){}E(int _x,int _y,int _z){x=_x,y=_y,z=_z;}}e[M*9];
inline bool cmp(const E&a,const E&b){return a.z<b.z;}
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
inline void add(int x,int y){
v[++ed]=y;nxt[ed]=g[x];g[x]=ed;
}
void dfs(int x,int y,int z){
z=max(z,a[x]);
if(z<0)ans-=z;
for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x,z);
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)for(j=1;j<=m;j++){
id[i][j]=++tot;
scanf("%d",&a[tot]);
}
for(i=1;i<=n;i++)for(j=1;j<=m;j++)for(x=-1;x<=1;x++)for(y=-1;y<=1;y++){
int nx=i+x,ny=j+y;
if(nx<1||nx>n||ny<1||ny>m)continue;
e[++ce]=E(id[i][j],id[nx][ny],max(a[id[i][j]],a[id[nx][ny]]));
}
sort(e+1,e+ce+1,cmp);
for(i=1;i<=tot;i++)f[i]=i;
for(i=1;i<=ce;i++)if(F(e[i].x)!=F(e[i].y)){
f[f[e[i].x]]=f[e[i].y];
add(e[i].x,e[i].y);
add(e[i].y,e[i].x);
}
scanf("%d%d",&i,&j);
dfs(id[i][j],0,-10000000);
printf("%lld",ans);
}
F. Fractal Tree
留坑。
G. Galactic Collegiate Programming Contest
用一個set維護所有嚴格比$1$好的隊伍，若別人過題則試情況插入set，若$1$過題則將set中最差的若干隊伍刪除。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
struct A
{
int g, t;
bool operator < (const A &b)const
{
if(g != b.g)return g > b.g;
return t < b.t;
}
}a[N];
multiset<A>sot;
int main()
{
while(~scanf("%d%d",&n, &m))
{
for(int i = 1; i <= n; ++i)
{
a[i].g = a[i].t = 0;
}
for(int i = 1; i <= m; ++i)
{
int o, p;
scanf("%d%d", &o, &p);
if(o == 1)
{
a[1].g += 1;
a[1].t += p;
}
else
{
if(a[o] < a[1])
{
sot.erase(sot.find(a[o]));
}
a[o].g += 1;
a[o].t += p;
sot.insert(a[o]);
}
while(!sot.empty() && !(*--sot.end() < a[1]))
{
sot.erase(--sot.end());
}
printf("%d\n", sot.size() + 1);
}
}
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復雜度&&優化】
*/
H. Hubtown
極角排序后求出每個人最近的$1$到$2$條火車線路，然后求最大流即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long ll;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 4e5 + 10, M = 2e6 + 10, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
int ST, ED, ID;
int first[N], w[M], cap[M], nxt[M];
void ins(int x, int y, int cap_)
{
w[++ID] = y;
cap[ID] = cap_;
nxt[ID] = first[x];
first[x] = ID;
w[++ID] = x;
cap[ID] = 0;
nxt[ID] = first[y];
first[y] = ID;
}
int d[N];
bool bfs()
{
MS(d, -1); d[ST] = 0;
queue<int>q; q.push(ST);
while(!q.empty())
{
int x = q.front(); q.pop();
for(int z = first[x]; z; z = nxt[z])if(cap[z])
{
int y = w[z];
if(d[y] == -1)
{
d[y] = d[x] + 1;
if(y == ED)return 1;
q.push(y);
}
}
}
return 0;
}
int dfs(int x, int all)
{
if(x == ED)return all;
int use = 0;
for(int z = first[x]; z; z = nxt[z])if(cap[z])
{
int y = w[z];
if(d[y] == d[x] + 1)
{
int tmp = dfs(y, min(cap[z], all - use));
cap[z] -= tmp;
cap[z ^ 1] += tmp;
use += tmp;
if(use == all)break;
}
}
if(use == 0)d[x] = -1;
return use;
}
int dinic()
{
int tmp = 0;
while(bfs())tmp += dfs(ST, inf);
return tmp;
}
struct A
{
int x, y, o;
}a[N];
struct B
{
int x, y, o,c;
}b[N];
struct E{
int x,y,t;
int sgn;
E(){}
E(int _x,int _y,int _t){
x=_x,y=_y,t=_t;
if(!x)sgn=y>0;
else sgn=x>0;
}
}e[400010];
inline bool cmpe(const E&a,const E&b){
if(a.sgn!=b.sgn)return a.sgn<b.sgn;
int t=a.x*b.y-a.y*b.x;
if(t)return t<0;
return a.t<b.t;
}
int pre[400010],suf[400010];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline bool point_on_line(const A&a,const B&b){
int d1=gcd(abs(a.x),abs(a.y)),d2=gcd(abs(b.x),abs(b.y));
return (a.x/d1==b.x/d2)&&(a.y/d1==b.y/d2);
}
struct Point{
ll x,y;
Point(){}
Point(ll _x,ll _y){x=_x,y=_y;}
};
inline ll cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}
inline ll sig(ll x){
if(x==0)return 0;
return x>0?1:-1;
}
typedef long double ld;
const ld epsss=1e-10;
struct Pointd{
ld x,y;
Pointd(){}
Pointd(ld _x,ld _y){x=_x,y=_y;}
};
inline ld crossd(const Pointd&a,const Pointd&b){return a.x*b.y-a.y*b.x;}
inline ll sigd(ld x){
if(fabs(x)<epsss)return 0;
return x>0?1:-1;
}
inline int distance_cmp(const A&_a,const B&_b,const B&_c){
Point a(_a.x,_a.y);
Point b(_b.x,_b.y);
Point c(_c.x,_c.y);
Point d;
if(!cross(b,c)){
d=Point(-b.y,b.x);
if(!cross(a,d))return 0;
if(sig(cross(d,a))==sig(cross(d,b)))return -1;
return 1;
}
ld L=sqrt(b.x*b.x+b.y*b.y);
ld R=sqrt(c.x*c.x+c.y*c.y);
Pointd aa(a.x,a.y);
Pointd bb(b.x,b.y);
Pointd cc(c.x,c.y);
Pointd dd(d.x,d.y);
bb.x*=R;
bb.y*=R;
cc.x*=L;
cc.y*=L;
dd=Pointd(bb.x+cc.x,bb.y+cc.y);
if(!sigd(crossd(aa,dd)))return 0;
if(sigd(crossd(dd,aa))==sigd(crossd(dd,bb)))return -1;
return 1;
}
int main()
{
while(~scanf("%d%d",&n, &m))
{
ST = 0;
ED = n + m + 1;
ID = 1; MS(first, 0);
for(int i = 1; i <= n; ++i)
{
scanf("%d%d", &a[i].x, &a[i].y);
a[i].o = i;
}
//sort a?
for(int i = 1; i <= m; ++i)
{
scanf("%d%d%d", &b[i].x, &b[i].y,&b[i].c);
b[i].o = i;
}
//sort b?
int ce=0;
for(int i=1;i<=n;i++){
e[++ce]=E(a[i].x,a[i].y,i);
}
for(int i=1;i<=m;i++){
e[++ce]=E(b[i].x,b[i].y,-i);
}
sort(e+1,e+ce+1,cmpe);
pre[0]=0;
for(int i=1;i<=ce;i++)if(e[i].t<0)pre[0]=-e[i].t;
for(int i=1;i<=ce;i++){
pre[i]=pre[i-1];
if(e[i].t<0)pre[i]=-e[i].t;
}
suf[ce+1]=0;
for(int i=ce;i;i--)if(e[i].t<0)suf[ce+1]=-e[i].t;
for(int i=ce;i;i--){
suf[i]=suf[i+1];
if(e[i].t<0)suf[i]=-e[i].t;
}
for(int i=1;i<=ce;i++)if(e[i].t>0){
int x=e[i].t;
int L=pre[i],R=suf[i];
if(L==R){
ins(x,L+n,1);
continue;
}
if(point_on_line(a[x],b[L])){
ins(x,L+n,1);
continue;
}
if(point_on_line(a[x],b[R])){
ins(x,R+n,1);
continue;
}
int t=distance_cmp(a[x],b[L],b[R]);
if(t<=0)ins(x,L+n,1);
if(t>=0)ins(x,R+n,1);
}
for(int i = 1; i <= n; ++i)
{
ins(ST, i, 1);
}
for(int i = 1; i <= m; ++i)
{
ins(n + i, ED, b[i].c);
}
//addedge: &&maybe use a little greedy method
printf("%d\n",dinic());
for(int i = 1; i <= n; ++i)
{
for(int z = first[i]; z; z = nxt[z])
{
int y = w[z];
if(y > n && cap[z] == 0)
{
printf("%d %d\n", i - 1, y - n - 1);
}
}
}
}
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復雜度&&優化】
*/
I. Import Spaghetti
枚舉起點，BFS求最小環。
#include<cstdio>
#include<map>
#include<cstring>
#include<iostream>
#include<sstream>
using namespace std;
const int N=555;
int n,i;
string name[N];
bool g[N][N];
map<string,int>id;
int ans=N,finS,finT;
int d[N],f[N],q[N],h,t;
inline int ask(string t){
string x="";
for(int i=0;i<t.size();i++)if(t[i]>='a'&&t[i]<='z')x.push_back(t[i]);
return id[x];
}
inline void ext(int x,int y,int z){
if(d[x]<0){
q[++t]=x;
d[x]=y;
f[x]=z;
}
}
void bfs(int S){
int i,j,x;
for(i=1;i<=n;i++)d[i]=-1;
h=1,t=0;
ext(S,0,0);
while(h<=t){
x=q[h++];
int y=d[x]+1;
for(i=1;i<=n;i++)if(g[x][i])ext(i,y,x);
}
for(i=1;i<=n;i++)if(d[i]>0&&g[i][S]){
int now=d[i]+1;
if(now<ans)ans=now,finS=S,finT=i;
}
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
cin>>name[i];
id[name[i]]=i;
}
for(i=1;i<=n;i++){
string tmp;int k;
cin>>tmp>>k;
char ss[2]; gets(ss);
while(k--)
{
string s;
getline(cin, s);
stringstream cinn(s);
int flag=1;
while(cinn>>s)
{
if(flag){flag=0;continue;}
int y=ask(s);
g[y][i]=1;
//printf("%d %d\n",i,y);
}
}
}
for(i=1;i<=n;i++)if(g[i][i]){
cout<<name[i]<<endl;
return 0;
}
for(i=1;i<=n;i++)bfs(i);
if(ans>=N){
puts("SHIP IT");
return 0;
}
//printf("%d %d %d\n",ans,finS,finT);
bfs(finS);
i=finT;
while(i){
cout<<name[i]<<" ";
i=f[i];
}
}
/*
4
a b c d
a 1
import d, b, c
b 2
import d
import c
c 1
import c
d 0
5
classa classb myfilec execd libe
classa 2
import classb
import myfilec, libe
classb 1
import execd
myfilec 1
import libe
execd 1
import libe
libe 0
5
classa classb myfilec execd libe
classa 2
import classb
import myfilec, libe
classb 1
import execd
myfilec 1
import libe
execd 1
import libe, classa
libe 0
*/
J. Judging Moose
按題意模擬即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int l, r;
int main()
{
while(~scanf("%d%d",&l, &r))
{
if(l + r == 0)
{
puts("Not a moose");
}
else if(l == r)
{
printf("Even %d\n", l + r);
}
else
{
printf("Odd %d\n", max(l, r) * 2);
}
}
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復雜度&&優化】
*/
K. Kayaking Trip
二分答案，貪心配對檢驗。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
int g[3], gg[3];
int s[3];
int c[N];
bool check(int aim)
{
gg[0] = g[0];
gg[1] = g[1];
gg[2] = g[2];
for(int i = 1; i <= m; ++i)
{
int need = aim / c[i] + (aim % c[i] > 0);
int jj = -1;
int kk = -1;
for(int j = 0; j < 3; ++j)
{
for(int k = j; k < 3; ++k)
{
int num = 1;
if(j == k)num = 2;
if(gg[j] >= num && gg[k] >= num && s[j] + s[k] >= need)
{
if(jj == -1 || s[j] + s[k] < s[jj] + s[kk])
{
jj = j;
kk = k;
}
}
}
}
if(jj == -1)return 0;
gg[jj] -= 1;
gg[kk] -= 1;
//
//printf("after ope %d: %d %d %d\n", i, gg[0], gg[1], gg[2]);
//
}
return 1;
}
int main()
{
while(~scanf("%d%d%d",&g[0], &g[1], &g[2]))
{
scanf("%d%d%d",&s[0], &s[1], &s[2]);
m = (g[0] + g[1] + g[2]) / 2;
for(int i = 1; i <= m; ++i)scanf("%d", &c[i]);
sort(c + 1, c + m + 1);
int l = c[1] * (s[0] + s[0]);
int r = c[m] * (s[2] + s[2]);
//
//l = r = 505;
//printf("l == %d r == %d\n", l, r);
//
int ans = -1;
while(l <= r)
{
int mid = (l + r + 1) / 2;
if(check(mid))
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
printf("%d\n", ans);
}
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復雜度&&優化】
*/
浙公網安備 33010602011771號