Submission #1001446

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

#define popcount(x) __builtin_popcount(x)

const int maxn = 16;
const int maxmask = 1 << 16;
const ld inf = 1e18;

int x[maxn], y[maxn], a[maxn];
ld ans[maxmask], answer[maxmask];
ld d[maxn][maxn];
ld mindist[maxmask][maxn];
int n;

inline ld shedge(int m1, int m2)
{
    ld answer = inf;
    for (int j = 0; j < n; j++) if (m1 & (1 << j)) answer = min(answer, mindist[m2][j]);
    return answer;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d%d", &x[i], &y[i], &a[i]);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++) d[i][j] = sqrt((ld)(x[i] - x[j]) * (x[i] - x[j]) + (ld)(y[i] - y[j]) * (y[i] - y[j]));
    }
    int km = 1 << n;
    for (int mask = 0; mask < km; mask++)
    {
        for (int i = 0; i < n; i++)
        {
            mindist[mask][i] = inf;
            for (int j = 0; j < n; j++) if (mask & (1 << j)) mindist[mask][i] = min(mindist[mask][i], d[i][j]);
        }
    }
    for (int i = 0; i < n; i++) ans[1 << i] = a[i];
    for (int mask = 1; mask < km; mask++) if (popcount(mask) > 1)
    {
        ans[mask] = -inf;
//         for (int i = 0; i < n; i++) if (mask & (1 << i))
//         {
//             ld d = mindist[mask ^ (1 << i)][i];
//             /*if (a[i] > d || ans[mask ^ (1 << i)] / (popcount(mask) - 1) > d)*/ ans[mask] = max(ans[mask], ans[mask ^ (1 << i)] + a[i] - d);
//         }
        for (int submask = (mask & (mask - 1)); submask > 0; submask = ((submask - 1) & mask))
        {
            ld d = shedge(submask, mask ^ submask);
            ans[mask] = max(ans[mask], ans[submask] + ans[mask ^ submask] - d);
        }
//         cout << mask << ' ' << ans[mask] << endl;
    }
//     cout.precision(20);
//     cout << ans[km - 1] / n << endl;
    for (int i = 0; i < n; i++) answer[1 << i] = a[i];
    for (int mask = 1; mask < km; mask++) if (popcount(mask) > 1)
    {
        answer[mask] = ans[mask] / popcount(mask);
        for (int submask = (mask & (mask - 1)); submask > 0; submask = ((submask - 1) & mask))
        {
            answer[mask] = max(answer[mask], min(answer[submask], answer[mask ^ submask]));
        }
    }
    cout.precision(20);
    cout << answer[km - 1] << endl;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:43:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:46:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x[i], &y[i], &a[i]);
                                             ^

Judge Result