Submission #2755515

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
/// 9:34

const int N = 15;
const long double eps = 1e-10;
typedef long long ll;

int n, i, j, x[N], y[N], A[N], cnt[1<<N];
ll a[1<<N];
long double apm[1<<N], dist[N+1], dp[1<<N], d[N][N];

long double solve()
{
    int mask, msk;
    for(mask = 1; mask < (1<<n); ++mask)
    {
        dp[mask] = 1.0 * (a[mask] - apm[mask]) / cnt[mask];
        for(msk = (mask-1) & mask; msk; msk = (msk-1) & mask)
            dp[mask] = max(dp[mask], min(dp[msk], dp[mask^msk]));
    }
    return dp[mask-1];
}

ll sq(int x) { return (ll)x*x; }

long double distant(int i, int j)
{
    return sqrt( sq(x[i] - x[j]) + sq(y[i] - y[j]) );
}

long double compute(int mask)
{
    int i, start;
    long double ans = 0;
    for(i=0; i<n; ++i)
        if(mask & (1<<i)) start = i;

    for(i=0; i<n; ++i) dist[i] = d[start][i];
    mask ^= (1<<start);

    while(mask)
    {
        start = n;
        for(i=0; i<n; ++i)
            if( (mask & (1<<i)) && dist[i] < dist[start] ) start = i;

        mask ^= (1<<start);
        ans += dist[start];

        for(i=0; i<n; ++i)
            if( (mask & (1<<i)) ) dist[i] = min(dist[i], d[start][i]);
    }
    return ans;
}

int main()
{
 //   freopen("input", "r", stdin);
 //   freopen("output", "w", stdout);
    cin.sync_with_stdio(false);

    cin >> n; dist[n] = 2e9;
    for(i=0; i<n; ++i)
        cin >> x[i] >> y[i] >> A[i];

    for(i=0; i<n; ++i)
        for(j=i; j<n; ++j)
            d[i][j] = d[j][i] = distant(i, j);

    for(i=1; i<(1<<n); ++i)
    {
        apm[i] = compute(i);
        cnt[i] = __builtin_popcount(i);
        for(j=0; j<n; ++j)
            if(i&(1<<j)) a[i] += A[j];
    }

    cout << setprecision(10) << fixed;
    cout << solve() << '\n';
    return 0;
}

Submission Info

Judge Result