Submission #22314551


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define inf 1000000007
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define rrep(i,n) for(int i = (int)n-1; i >= 0; --i)
#define srep(i,a,b) for(int i = (int)a; i < (int)(b); ++i)
#define all(x) (x).begin(),(x).end()
#define SUM(v) accumulate(all(v), 0LL)
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define SZ(c) (int)(c).size()
// pair出力
template<typename T, typename U>
ostream& operator << (ostream& os, pair<T, U> pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// map出力
template<typename T, typename U>
ostream& operator << (ostream& os, map<T, U>& map_var) {
    os << "{";
    for(auto itr = map_var.begin(); itr != map_var.end(); itr++){
        os << "(" << itr->first << ", " << itr->second << ")";
        itr++;
        if(itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set 出力
template<typename T>
ostream& operator << (ostream& os, set<T>& set_var) {
    os << "{";
    for(auto itr = set_var.begin(); itr != set_var.end(); itr++){
        os << (*itr);
        ++itr;
        if(itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
#define overload2(_1, _2, name, ...) name
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define VEC(type, name, size)                                                                                                                                  \
    vector<type> name(size);                                                                                                                                   \
    IN(name)
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define VV(type, name, h, w)                                                                                                                                   \
    vector<vector<type>> name(h, vector<type>(w));                                                                                                             \
    IN(name)
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)                                                                                                                         \
    vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define INT(...)                                                                                                                                               \
    int __VA_ARGS__;                                                                                                                                           \
    IN(__VA_ARGS__)
#define LL(...)                                                                                                                                                \
    ll __VA_ARGS__;                                                                                                                                            \
    IN(__VA_ARGS__)
#define STR(...)                                                                                                                                               \
    string __VA_ARGS__;                                                                                                                                        \
    IN(__VA_ARGS__)
#define CHR(...)                                                                                                                                               \
    char __VA_ARGS__;                                                                                                                                          \
    IN(__VA_ARGS__)
#define DBL(...)                                                                                                                                               \
    double __VA_ARGS__;                                                                                                                                        \
    IN(__VA_ARGS__)
int scan() { return getchar(); }
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }
template <class T> void scan(vector<T> &);
template <class T> void scan(vector<T> &a) {
    for(auto &i : a) scan(i);
}
template <class T> void scan(T &a) { cin >> a; }
void IN() {}
template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {
    scan(head);
    IN(tail...);
}
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
void YES(bool t = 1) { cout << YESNO[t] << endl; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << endl; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << endl; }
void no(bool t = 1) { yes(!t); }
#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define dbg(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define dbg(...) (void(0))
#define dump(x) (void(0))
#endif
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
template <class T> T ceil(T x, T y) {assert(y >= 1);return (x > 0 ? (x + y - 1) / y : x / y);}
template <class T> T floor(T x, T y) {assert(y >= 1);return (x > 0 ? x / y : (x + y - 1) / y);}
vector<int> iota(int n) {vector<int> a(n);iota(all(a), 0);return a;}
template <class T> T POW(T x, int n) {T res = 1;for(; n; n >>= 1, x *= x){if(n & 1) res *= x;}return res;}
ll pow2(int i) { return 1LL << i; }
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int lowbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); }
int lowbit(ll a) { return a == 0 ? 64 : __builtin_ctzll(a); }
// int allbit(int n) { return (1 << n) - 1; }
ll allbit(ll n) { return (1LL << n) - 1; }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(int i) { return i && (i & -i) == i; }


template <class S> void fold_in(vector<S> &v) {}
template <typename Head, typename... Tail, class S> void fold_in(vector<S> &v, Head &&a, Tail &&...tail) {
    for(auto e : a) v.emplace_back(e);
    fold_in(v, tail...);
}
template <class S> void renumber(vector<S> &v) {}
template <typename Head, typename... Tail, class S> void renumber(vector<S> &v, Head &&a, Tail &&...tail) {
    for(auto &&e : a) e = lb(v, e);
    renumber(v, tail...);
}
template <class S, class... Args> void zip(vector<S> &head, Args &&...args) {
    vector<S> v;
    fold_in(v, head, args...);
    sort(all(v)), v.erase(unique(all(v)), v.end());
    renumber(v, head, args...);
}
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}

class UnionFind {
private:
    int sz;
    vector<int> par, nrank;
public:
    UnionFind(){}
    UnionFind(int node_size) : sz(node_size), par(sz), nrank(sz, 0){
        iota(par.begin(), par.end(), 0);
    }
    int find(int x){
        if(par[x] == x) return x;
        else return par[x] = find(par[x]);
    }
    void unite(int x,int y){
        x = find(x), y = find(y);
        if(x == y) return;
        if(nrank[x] < nrank[y]) swap(x,y);
        par[y] = x;
        if(nrank[x] == nrank[y]) nrank[x]++;
    }
    bool same(int x,int y){
        return find(x) == find(y);
    }
};

template<typename T> class Kruskal{
public:
    struct edge{
        int u,v;
        T cost;
        bool operator<(const edge& another) const {
            return cost < another.cost;
        }
    };
    vector<edge> es;
    int V;
    Kruskal(int node_size) : V(node_size){}
    void add_edge(int u,int v,T cost){
        es.push_back((edge){u,v,cost});
    }
    T solve(){
        UnionFind uf(V);
        T res = 0;
        int cnt = 0;
        sort(es.begin(),es.end());
        for(edge& e : es){
            if(!uf.same(e.u,e.v)){
                uf.unite(e.u,e.v);
                res += e.cost;
                cnt++;
                if(cnt == V-1){
                    break;
                }
            }
        }
        return res;
    }
};

double cost[1<<15];
double dp[1<<15];

int main(){
    INT(n);    
    vector<double> x(n),y(n),a(n);
    rep(i,n)cin >> x[i] >> y[i] >> a[i];
    rep(bits,1<<n){
        if(bits==0)continue;
        int k = popcount(bits);
        vector<double>p,q;
        double s = 0;
        rep(i,n){
            if((bits>>i)&1){
                p.push_back(x[i]);
                q.push_back(y[i]);
                s += a[i];
            }
        }
        Kruskal<double> ks(k);
        rep(i,k){
            rep(j,i){
                ks.add_edge(j,i,sqrt((p[i]-p[j])*(p[i]-p[j])+(q[i]-q[j])*(q[i]-q[j])));
            }
        }
        s -= ks.solve();
        cost[bits] = (s)/(double)(k);
    }
    Fill(dp,-inf);
    dp[0] = inf;
    rep(x,1<<n){
        for (int y = x; y < (1 << n); y = (y + 1) | x) {
            chmax(dp[y],min(dp[x],cost[x^y]));
        }
    }
    cout << fixed << setprecision(30) <<  dp[(1<<n)-1] << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Water Distribution
User mtsd
Language C++ (GCC 9.2.1)
Score 1000
Code Size 10467 Byte
Status AC
Exec Time 72 ms
Memory 4332 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 2
AC × 46
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 70 ms 4156 KB
001.txt AC 68 ms 4160 KB
002.txt AC 68 ms 4276 KB
003.txt AC 66 ms 4212 KB
004.txt AC 69 ms 4196 KB
005.txt AC 68 ms 4180 KB
006.txt AC 67 ms 4220 KB
007.txt AC 67 ms 4144 KB
008.txt AC 70 ms 4144 KB
009.txt AC 69 ms 4160 KB
010.txt AC 70 ms 4332 KB
011.txt AC 68 ms 4148 KB
012.txt AC 67 ms 4316 KB
013.txt AC 69 ms 4136 KB
014.txt AC 67 ms 4192 KB
015.txt AC 70 ms 4296 KB
016.txt AC 70 ms 4180 KB
017.txt AC 69 ms 4292 KB
018.txt AC 68 ms 4148 KB
019.txt AC 68 ms 4160 KB
020.txt AC 69 ms 4096 KB
021.txt AC 67 ms 4220 KB
022.txt AC 67 ms 4220 KB
023.txt AC 69 ms 4156 KB
024.txt AC 66 ms 4200 KB
025.txt AC 68 ms 4160 KB
026.txt AC 68 ms 4220 KB
027.txt AC 67 ms 4156 KB
028.txt AC 68 ms 4156 KB
029.txt AC 71 ms 4276 KB
030.txt AC 69 ms 4148 KB
031.txt AC 67 ms 4164 KB
032.txt AC 69 ms 4120 KB
033.txt AC 68 ms 4160 KB
034.txt AC 66 ms 4148 KB
035.txt AC 72 ms 4256 KB
036.txt AC 67 ms 4180 KB
037.txt AC 71 ms 4164 KB
038.txt AC 69 ms 4164 KB
039.txt AC 70 ms 4196 KB
040.txt AC 2 ms 3844 KB
041.txt AC 2 ms 4000 KB
042.txt AC 2 ms 3864 KB
043.txt AC 4 ms 3924 KB
example0.txt AC 3 ms 3912 KB
example1.txt AC 68 ms 4164 KB