Submission #1000882


Source Code Expand

#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define F0(i,n) for (int i = 0; i < n; i++)
#define F1(i,n) for (int i = 1; i <= n; i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define SZ(x) ((int)x.size())
const double eps = 1e-10;
const int inf = 1000000009;
int i, j, k, m, n, l;
int ans;
int x[15], y[15], a[15];
double d[15][15], e[15], dp[15][1<<15];

int ok(double R) {
	F0(i, n) e[i] = a[i] - R;

	F0(i, n) F0(j, (1 << n)) dp[i][j] = -1e100;
	F0(i, n) dp[i][(1 << i)] = e[i];

	F0(mask, (1 << n)) F0(i, n) if ((1 << i)&mask) {
		F0(j, n) if (((1 << j)&mask) == 0) {
			int mm = mask | (1 << j);

			if (dp[i][mask] >= 0) {
				dp[j][mm] = max(dp[j][mm], e[j]);
			}

			if (e[i] < 0 && e[j] < 0) continue;
			//if (e[i] >= 0 && e[j] >= 0) continue;

			double total = dp[i][mask] + e[j] - d[i][j];

			dp[i][mm] = max(dp[i][mm], total);
			dp[j][mm] = max(dp[j][mm], total);
		}
	}
	F0(i, n) if (dp[i][(1 << n) - 1] >= 0) return 1;
	return 0;
}

int main() {
	//freopen("x.in", "r", stdin);

	cin >> n;
	F0(i, n) {
		cin >> x[i] >> y[i] >> a[i];
	}

	F0(i, n) F0(j, n) d[i][j] = hypot(1.0*x[i] - x[j], 1.0*y[i] - y[j]);

	double P = 0.0, Q = 1e9, R;
	F0(it, 100) {
		R = (P + Q) / 2;
		if (ok(R)) P = R; else Q = R;
	}
	printf("%.10lf\n", P);
	return 0;
}

Submission Info

Submission Time
Task E - Water Distribution
User USA
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1594 Byte
Status WA
Exec Time 2094 ms
Memory 4224 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 2
AC × 21
WA × 5
TLE × 20
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 TLE 2034 ms 4096 KB
001.txt TLE 2008 ms 4096 KB
002.txt TLE 2018 ms 4096 KB
003.txt TLE 2058 ms 4096 KB
004.txt TLE 2021 ms 4096 KB
005.txt TLE 2007 ms 4096 KB
006.txt WA 1966 ms 4096 KB
007.txt TLE 2032 ms 4224 KB
008.txt TLE 2046 ms 4096 KB
009.txt TLE 2053 ms 4096 KB
010.txt TLE 2033 ms 4096 KB
011.txt TLE 2023 ms 4096 KB
012.txt TLE 2022 ms 4096 KB
013.txt TLE 2068 ms 4096 KB
014.txt TLE 2025 ms 4096 KB
015.txt TLE 2051 ms 4096 KB
016.txt WA 1998 ms 4096 KB
017.txt TLE 2011 ms 4096 KB
018.txt WA 1996 ms 4096 KB
019.txt TLE 2030 ms 4096 KB
020.txt AC 1944 ms 4096 KB
021.txt TLE 2031 ms 4096 KB
022.txt TLE 2094 ms 4096 KB
023.txt AC 1950 ms 4096 KB
024.txt AC 1934 ms 4096 KB
025.txt AC 1967 ms 4096 KB
026.txt TLE 2003 ms 4096 KB
027.txt WA 1997 ms 4096 KB
028.txt AC 1963 ms 4224 KB
029.txt AC 1942 ms 4096 KB
030.txt AC 1983 ms 4096 KB
031.txt AC 1938 ms 4096 KB
032.txt AC 1908 ms 4096 KB
033.txt AC 1953 ms 4096 KB
034.txt AC 1919 ms 4096 KB
035.txt AC 1920 ms 4096 KB
036.txt AC 1915 ms 4096 KB
037.txt AC 1912 ms 4096 KB
038.txt AC 1910 ms 4096 KB
039.txt AC 1922 ms 4096 KB
040.txt AC 3 ms 256 KB
041.txt AC 3 ms 256 KB
042.txt AC 3 ms 256 KB
043.txt WA 7 ms 256 KB
example0.txt AC 3 ms 256 KB
example1.txt AC 1998 ms 4096 KB