Submission #1000884


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, 50) {
		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 1593 Byte
Status WA
Exec Time 1078 ms
Memory 4224 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 1
WA × 1
AC × 22
WA × 24
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 WA 1050 ms 4096 KB
001.txt WA 1039 ms 4096 KB
002.txt AC 1054 ms 4096 KB
003.txt WA 1056 ms 4096 KB
004.txt WA 1066 ms 4096 KB
005.txt WA 1038 ms 4096 KB
006.txt WA 1015 ms 4096 KB
007.txt WA 1050 ms 4096 KB
008.txt WA 1058 ms 4096 KB
009.txt WA 1065 ms 4096 KB
010.txt WA 1046 ms 4096 KB
011.txt WA 1041 ms 4096 KB
012.txt WA 1040 ms 4096 KB
013.txt WA 1077 ms 4096 KB
014.txt WA 1045 ms 4224 KB
015.txt WA 1053 ms 4096 KB
016.txt WA 1034 ms 4096 KB
017.txt WA 1035 ms 4096 KB
018.txt WA 1024 ms 4096 KB
019.txt WA 1053 ms 4096 KB
020.txt AC 1022 ms 4096 KB
021.txt AC 1053 ms 4096 KB
022.txt WA 1078 ms 4096 KB
023.txt AC 1016 ms 4096 KB
024.txt AC 1018 ms 4096 KB
025.txt AC 1028 ms 4096 KB
026.txt WA 1033 ms 4096 KB
027.txt WA 1034 ms 4096 KB
028.txt AC 1022 ms 4096 KB
029.txt AC 1016 ms 4096 KB
030.txt AC 1030 ms 4096 KB
031.txt AC 1014 ms 4096 KB
032.txt AC 999 ms 4096 KB
033.txt AC 1012 ms 4096 KB
034.txt AC 1001 ms 4096 KB
035.txt AC 1001 ms 4096 KB
036.txt AC 999 ms 4096 KB
037.txt AC 989 ms 4096 KB
038.txt AC 989 ms 4096 KB
039.txt AC 997 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 5 ms 256 KB
example0.txt WA 3 ms 256 KB
example1.txt AC 1057 ms 4096 KB