TOKI Regular Open Contest #16 F問目 - Radio Radius

Source

TOKI Regular Open Contest #16
問題文
Problemset (TOKI Regular Open Contest #16)

問題概要

省略

解法

省略

cLayversion 20201123-1)のコード

C++に変換後のコードはこちら

int N, M; ll R, X[2d5], Y[2d5], A[20], B[20], C[20];
int ok[2d5], cnt[2d6], zt[2d6];
ll res[2d5], cost[2d6];
{
  rd(N,M,R,(X,Y)(N),(A,B,C)(M));
  R *= R;
  rep(i,N) rep(j,M) if( (X[i]-A[j])**2 + (Y[i]-B[j])**2 <= R ) ok[i] |= (1<<j);
  rep(i,N) cnt[ok[i]]++;
  ZetaTransform(1<<M, cnt, zt);
  subsetSum(M, C, cost);

  rep(i,N) res[i] = ll_inf;
  rep(mask,1<<M){
    i = N - zt[((1<<M)-1) ^ mask];
    if(i==0) continue;
    res[i-1] <?= cost[mask];
  }

  rrep(i,1,N) res[i-1] <?= res[i];
  rep(i,N) if(res[i]==ll_inf) res[i] = -1;
  wtLn(res(N));
}

Current time: 2021年09月27日22時51分28秒
Last modified: 2020年11月23日16時58分35秒 (by laycrs)
Tags: Competitive_Programming_Incomplete TOKI
トップページに戻る

Logged in as: unknown user (not login)

ログイン: