Recently I've been submit some pratice code to solve the Edgy Baking problem of Google code jam but there always is some error in my output, even thought the difference never exceed 0.01 as I've tested some random input. Can someone please check it ?↵
↵
#include <iostream>↵
#include <bits/stdc++.h>↵
using namespace std;↵
float ANS[200];↵
int a[200];↵
float b[200];↵
struct P{int mi; float mx;};↵
P info[200];↵
float leftover;↵
float M;↵
bool comparemi(const P&x, const P&y){return x.mi<y.mi;};↵
bool comparemx(const P&x, const P&y){return x.mx<y.mx;}↵
float solve(int h, float ans, float leftover, float M){↵
if(h>=3&&info[1].mi+info[2].mi+info[3].mi<=M){ans=M;}↵
else{↵
if(info[h].mi<=M/2.000){sort(info+1,info+1+h,comparemx);↵
if(h>=2){ans=max(ans,min(M,info[h].mx+info[h-1].mx+leftover));}↵
else{ans=max(ans,min(M,info[h].mx+leftover));};↵
}↵
if(info[h].mi>M/2.000){if(info[h].mi<=M){if(h==1||info[h].mi+info[1].mi>M){ans=max(min(M,info[h].mx+leftover),ans);}↵
else{ans=M;}↵
}↵
else ans=max(solve(h-1,ans,leftover,M),ans);↵
};↵
};return ans;}↵
int main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.precision(15);↵
int T;↵
cin>>T;↵
for(int nb=1;nb<T+1;nb++){↵
int u,v,N;↵
float P;↵
float peri=0;↵
float leftover=0;↵
cin>>N>>P;↵
for(int i=1;i<N+1;i++){cin>>u>>v;↵
a[i]=min(u,v);b[i]=sqrt(u*u+v*v);peri+=2*u+2*v;↵
}↵
float M;↵
M=(P-peri)/2.000;↵
int h=0;↵
for(int i=1;i<N+1;i++){if(a[i]<=M*(1-1/sqrt(2)))leftover+=b[i];↵
else {h++;info[h].mi=a[i];info[h].mx=b[i];}↵
}↵
sort(info+1,info+h+1,comparemi);↵
float ans=0;↵
ANS[nb]=2*solve(h,ans,leftover,M)+peri;}↵
for(int nb=1;nb<T+1;nb++)↵
cout<<"Case #"<<nb<<": "<<ANS[nb]<<endl;↵
↵
return 0;↵
}https://pastebin.com/526V81qR↵
#include <iostream>↵
#include <bits/stdc++.h>↵
using namespace std;↵
float ANS[200];↵
int a[200];↵
float b[200];↵
struct P{int mi; float mx;};↵
P info[200];↵
float leftover;↵
float M;↵
bool comparemi(const P&x, const P&y){return x.mi<y.mi;};↵
bool comparemx(const P&x, const P&y){return x.mx<y.mx;}↵
float solve(int h, float ans, float leftover, float M){↵
if(h>=3&&info[1].mi+info[2].mi+info[3].mi<=M){ans=M;}↵
else{↵
if(info[h].mi<=M/2.000){sort(info+1,info+1+h,comparemx);↵
if(h>=2){ans=max(ans,min(M,info[h].mx+info[h-1].mx+leftover));}↵
else{ans=max(ans,min(M,info[h].mx+leftover));};↵
}↵
if(info[h].mi>M/2.000){if(info[h].mi<=M){if(h==1||info[h].mi+info[1].mi>M){ans=max(min(M,info[h].mx+leftover),ans);}↵
else{ans=M;}↵
}↵
else ans=max(solve(h-1,ans,leftover,M),ans);↵
};↵
};return ans;}↵
int main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.precision(15);↵
int T;↵
cin>>T;↵
for(int nb=1;nb<T+1;nb++){↵
int u,v,N;↵
float P;↵
float peri=0;↵
float leftover=0;↵
cin>>N>>P;↵
for(int i=1;i<N+1;i++){cin>>u>>v;↵
a[i]=min(u,v);b[i]=sqrt(u*u+v*v);peri+=2*u+2*v;↵
}↵
float M;↵
M=(P-peri)/2.000;↵
int h=0;↵
for(int i=1;i<N+1;i++){if(a[i]<=M*(1-1/sqrt(2)))leftover+=b[i];↵
else {h++;info[h].mi=a[i];info[h].mx=b[i];}↵
}↵
sort(info+1,info+h+1,comparemi);↵
float ans=0;↵
ANS[nb]=2*solve(h,ans,leftover,M)+peri;}↵
for(int nb=1;nb<T+1;nb++)↵
cout<<"Case #"<<nb<<": "<<ANS[nb]<<endl;↵
↵
return 0;↵
}
