Submission #3515417
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=(b); ++i)
#define per(i,a,b) for (int i=(a); i>=(b); --i)
#define REP(i,n) for (int i=(0); i<(n); ++i)
#define cmin(x,y) ((y)<(x)?(x)=(y):0)
#define cmax(x,y) ((y)>(x)?(x)=(y):0)
#define sqr(x) ((x) * (x))
using namespace std;
const int N = 16;
double x[N], y[N], a[N], d[N][N], f[1<<N];
int n;
int main() {
scanf("%d", &n);
rep (i, 1, n) scanf("%lf%lf%lf", &x[i], &y[i], &a[i]);
rep (i, 1, n) rep (j, 1, n)
d[i][j] = sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
fill(f, f + (1 << n), 1e99); f[0] = 0;
REP (i, n) f[1<<i] = 0;
REP (s, 1 << n) rep (i, 0, n - 1) rep (j, 0, n - 1)
if ((s >> i & 1) && !(s >> j & 1))
cmin(f[s|(1<<j)], f[s] + d[i+1][j+1]);
REP (s, 1 << n) {
f[s] = -f[s];
REP (i, n) if (s >> i & 1) f[s] += a[i+1];
f[s] /= __builtin_popcount(s);
for (int t=(s-1)&s; t; t=(t-1)&s)
cmax(f[s], min(f[t], f[s-t]));
}
printf("%.10lf\n", f[(1<<n)-1]);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Water Distribution |
User |
Cyanic |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
991 Byte |
Status |
AC |
Exec Time |
74 ms |
Memory |
512 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:15:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:16:55: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep (i, 1, n) scanf("%lf%lf%lf", &x[i], &y[i], &a[i]);
^
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 |
67 ms |
512 KB |
001.txt |
AC |
68 ms |
512 KB |
002.txt |
AC |
61 ms |
512 KB |
003.txt |
AC |
66 ms |
512 KB |
004.txt |
AC |
70 ms |
512 KB |
005.txt |
AC |
65 ms |
512 KB |
006.txt |
AC |
71 ms |
512 KB |
007.txt |
AC |
66 ms |
512 KB |
008.txt |
AC |
68 ms |
512 KB |
009.txt |
AC |
69 ms |
512 KB |
010.txt |
AC |
71 ms |
512 KB |
011.txt |
AC |
72 ms |
512 KB |
012.txt |
AC |
70 ms |
512 KB |
013.txt |
AC |
65 ms |
512 KB |
014.txt |
AC |
70 ms |
512 KB |
015.txt |
AC |
74 ms |
512 KB |
016.txt |
AC |
63 ms |
512 KB |
017.txt |
AC |
71 ms |
512 KB |
018.txt |
AC |
69 ms |
512 KB |
019.txt |
AC |
65 ms |
512 KB |
020.txt |
AC |
54 ms |
512 KB |
021.txt |
AC |
63 ms |
512 KB |
022.txt |
AC |
62 ms |
512 KB |
023.txt |
AC |
56 ms |
512 KB |
024.txt |
AC |
57 ms |
512 KB |
025.txt |
AC |
52 ms |
512 KB |
026.txt |
AC |
58 ms |
512 KB |
027.txt |
AC |
54 ms |
512 KB |
028.txt |
AC |
53 ms |
512 KB |
029.txt |
AC |
55 ms |
512 KB |
030.txt |
AC |
52 ms |
512 KB |
031.txt |
AC |
54 ms |
512 KB |
032.txt |
AC |
51 ms |
512 KB |
033.txt |
AC |
51 ms |
512 KB |
034.txt |
AC |
49 ms |
512 KB |
035.txt |
AC |
49 ms |
512 KB |
036.txt |
AC |
48 ms |
512 KB |
037.txt |
AC |
49 ms |
512 KB |
038.txt |
AC |
50 ms |
512 KB |
039.txt |
AC |
50 ms |
512 KB |
040.txt |
AC |
1 ms |
256 KB |
041.txt |
AC |
1 ms |
256 KB |
042.txt |
AC |
1 ms |
256 KB |
043.txt |
AC |
1 ms |
256 KB |
example0.txt |
AC |
1 ms |
256 KB |
example1.txt |
AC |
59 ms |
512 KB |