Submission #1003864
Source Code Expand
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<utility>
#include<functional>
#include<iomanip>
#include<sstream>
#include<ctime>
#include<cassert>
using namespace std;
#define y0 y0z
#define y1 y1z
#define yn ynz
#define j0 j0z
#define j1 j1z
#define jn jnz
#define tm tmz
#define buli(x) (__builtin_popcountll(x))
#define bur0(x) (__builtin_ctzll(x))
#define bul2(x) (63-__builtin_clzll(x))
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fil(a,b) memset((a),(b),sizeof(a))
#define cl(a) fil(a,0)
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++)
#define rep(i,a,b) for (int i=(a),_ed=(b);i<_ed;i++)
#define per(i,a,b) for (int i=(b)-1,_ed=(a);i>=_ed;i--)
#define forg(i,gu) for (int i=gu;~i;i=e[i].next)
#define pw(x) ((ll(1))<<(x))
#define upmo(a,b) (((a)=((a)+(b))%mo)<0?(a)+=mo:(a))
#define mmo(a,b) (((a)=1ll*(a)*(b)%mo)<0?(a)+=mo:(a))
void getre(){int x=0;printf("%d\n",1/x);}
void gettle(){int res=1;while(1)res<<=1;printf("%d\n",res);}
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}
template<typename N,typename PN>inline N flo(N a,PN b){return a>=0?a/b:-((-a-1)/b)-1;}
template<typename N,typename PN>inline N cei(N a,PN b){return a>0?(a-1)/b+1:-(-a/b);}
template<typename N>N gcd(N a,N b){return b?gcd(b,a%b):a;}
template<typename N>inline int sgn(N a){return a>0?1:(a<0?-1:0);}
#if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L)
#define lld "%I64d"
#else
#define lld "%lld"
#endif
inline void gn(long long&x){
int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');c=='-'?(sg=-1,x=0):(x=c-'0');
while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';x*=sg;
}
inline void gn(int&x){long long t;gn(t);x=t;}
inline void gn(unsigned long long&x){long long t;gn(t);x=t;}
inline void gn(double&x){double t;scanf("%lf",&t);x=t;}
inline void gn(long double&x){double t;scanf("%lf",&t);x=t;}
inline void gs(char *s){scanf("%s",s);}
inline void gc(char &c){while((c=getchar())>126 || c<33);}
inline void pc(char c){putchar(c);}
#ifdef JCVB
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
typedef long long ll;
typedef double db;
inline ll sqr(ll a){return a*a;}
inline db sqrf(db a){return a*a;}
const int inf=0x3f3f3f3f;
const db pi=3.14159265358979323846264338327950288L;
const db eps=1e-6;
//const int mo=0;
//int qp(int a,ll b){int n=1;do{if(b&1)n=1ll*n*a%mo;a=1ll*a*a%mo;}while(b>>=1);return n;}
int n;
struct pkt{
int x,y;
void read(){gn(x);gn(y);}
ll dissq(){return 1ll*x*x+1ll*y*y;}
friend pkt operator+(const pkt&a,const pkt&b){return (pkt){a.x+b.x,a.y+b.y};}
friend pkt operator-(const pkt&a,const pkt&b){return (pkt){a.x-b.x,a.y-b.y};}
friend pkt operator-(const pkt&a){return (pkt){-a.x,-a.y};}
friend ll dot(const pkt&a,const pkt&b){return 1ll*a.x*b.x+1ll*a.y*b.y;}
friend ll cro(const pkt&a,const pkt&b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
friend bool operator<(const pkt&a,const pkt&b){return a.y==b.y?a.x<b.x:a.y<b.y;}
/*friend bool operator<(const pkt&a,const pkt&b){
int aa=a.y>0 || a.y==0&& a.x>0;
int bb=b.y>0 || b.y==0&& b.x>0;
if(aa!=bb)return aa<bb;
else return cro(a,b)>0;
}*/
}p[15];
db mst[1<<15];
int fa[15];
int gf(int x){
return x==fa[x]?x:fa[x]=gf(fa[x]);
}
bool un(int u,int v){
u=gf(u);v=gf(v);
if(u!=v){
fa[u]=v;
return 1;
}
return 0;
}
struct edg{
int u,v;
db x;
}ee[1111];
int cmp(const edg&a,const edg&b){
return a.x<b.x;
}
int etot;
db gao(int b){
etot=0;
rep(i,0,n)fa[i]=i;
rep(i,0,n)if(pw(i)&b)rep(j,i+1,n)if(pw(j)&b){
ee[++etot]=(edg){i,j,sqrt((p[i]-p[j]).dissq())};
}
sort(ee+1,ee+1+etot,cmp);
db su=0.0;
rep(i,1,etot+1){
if(un(ee[i].u,ee[i].v))su+=ee[i].x;
}
return su;
}
db ini[15];
db f[1<<15];
int main()
{
#ifdef JCVB
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int _time_jc=clock();
#endif
gn(n);
rep(i,0,n){
p[i].read();
gn(ini[i]);
}
rep(b,1,pw(n)){
mst[b]=gao(b);
}
rep(b,1,pw(n)){
db mia=1e18;
db su=0.0;
int cnt=0;
rep(i,0,n)if(pw(i)&b){
upmin(mia,ini[i]);
su+=ini[i];
cnt++;
}
f[b]=mia;
su-=mst[b];
upmax(su,0.0);
su/=cnt;
upmax(f[b],su);
}
f[0]=0.0;
rep(b,1,pw(n)){
for (int x=b;x;x=(x-1)&b){
upmax(f[b],min(f[x],f[b^x]));
}
}
printf("%.10lf\n",f[pw(n)-1]);
#ifdef JCVB
debug("time: %d\n",int(clock()-_time_jc));
#endif
return 0;
}
Submission Info
Submission Time
2016-11-30 14:24:07+0900
Task
E - Water Distribution
User
jcvb
Language
C++14 (GCC 5.4.1)
Score
1000
Code Size
4934 Byte
Status
AC
Exec Time
78 ms
Memory
768 KB
Compile Error
./Main.cpp: In function ‘void gn(double&)’:
./Main.cpp:66:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
inline void gn(double&x){double t;scanf("%lf",&t);x=t;}
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1000 / 1000
Status
Set Name
Test Cases
Sample
example0.txt, example1.txt
All
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, example0.txt, example1.txt
Case Name
Status
Exec Time
Memory
000.txt
AC
68 ms
768 KB
001.txt
AC
67 ms
768 KB
002.txt
AC
68 ms
768 KB
003.txt
AC
67 ms
768 KB
004.txt
AC
67 ms
768 KB
005.txt
AC
66 ms
768 KB
006.txt
AC
68 ms
768 KB
007.txt
AC
67 ms
768 KB
008.txt
AC
68 ms
768 KB
009.txt
AC
67 ms
768 KB
010.txt
AC
67 ms
768 KB
011.txt
AC
67 ms
768 KB
012.txt
AC
68 ms
768 KB
013.txt
AC
68 ms
768 KB
014.txt
AC
67 ms
768 KB
015.txt
AC
78 ms
768 KB
016.txt
AC
68 ms
768 KB
017.txt
AC
68 ms
768 KB
018.txt
AC
67 ms
768 KB
019.txt
AC
68 ms
768 KB
020.txt
AC
68 ms
768 KB
021.txt
AC
68 ms
768 KB
022.txt
AC
67 ms
768 KB
023.txt
AC
67 ms
768 KB
024.txt
AC
67 ms
768 KB
025.txt
AC
66 ms
768 KB
026.txt
AC
68 ms
768 KB
027.txt
AC
67 ms
768 KB
028.txt
AC
67 ms
768 KB
029.txt
AC
67 ms
768 KB
030.txt
AC
68 ms
768 KB
031.txt
AC
67 ms
768 KB
032.txt
AC
66 ms
768 KB
033.txt
AC
68 ms
768 KB
034.txt
AC
65 ms
768 KB
035.txt
AC
67 ms
768 KB
036.txt
AC
68 ms
768 KB
037.txt
AC
66 ms
768 KB
038.txt
AC
67 ms
768 KB
039.txt
AC
67 ms
768 KB
040.txt
AC
3 ms
256 KB
041.txt
AC
3 ms
256 KB
042.txt
AC
3 ms
256 KB
043.txt
AC
3 ms
256 KB
example0.txt
AC
3 ms
256 KB
example1.txt
AC
68 ms
768 KB