fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. template<class S, class T> inline S min_L(S a,T b){
  5.   return a<=b?a:b;
  6. }
  7. inline int my_getchar_unlocked(){
  8.   static char buf[1048576];
  9.   static int s = 1048576;
  10.   static int e = 1048576;
  11.   if(s == e && e == 1048576){
  12.     e = fread_unlocked(buf, 1, 1048576, stdin);
  13.     s = 0;
  14.   }
  15.   if(s == e){
  16.     return EOF;
  17.   }
  18.   return buf[s++];
  19. }
  20. inline void rd(int &x){
  21.   int k;
  22.   int m=0;
  23.   x=0;
  24.   for(;;){
  25.     k = my_getchar_unlocked();
  26.     if(k=='-'){
  27.       m=1;
  28.       break;
  29.     }
  30.     if('0'<=k&&k<='9'){
  31.       x=k-'0';
  32.       break;
  33.     }
  34.   }
  35.   for(;;){
  36.     k = my_getchar_unlocked();
  37.     if(k<'0'||k>'9'){
  38.       break;
  39.     }
  40.     x=x*10+k-'0';
  41.   }
  42.   if(m){
  43.     x=-x;
  44.   }
  45. }
  46. inline void rd(long long &x){
  47.   int k;
  48.   int m=0;
  49.   x=0;
  50.   for(;;){
  51.     k = my_getchar_unlocked();
  52.     if(k=='-'){
  53.       m=1;
  54.       break;
  55.     }
  56.     if('0'<=k&&k<='9'){
  57.       x=k-'0';
  58.       break;
  59.     }
  60.   }
  61.   for(;;){
  62.     k = my_getchar_unlocked();
  63.     if(k<'0'||k>'9'){
  64.       break;
  65.     }
  66.     x=x*10+k-'0';
  67.   }
  68.   if(m){
  69.     x=-x;
  70.   }
  71. }
  72. struct MY_WRITER{
  73.   char buf[1048576];
  74.   int s;
  75.   int e;
  76.   MY_WRITER(){
  77.     s = 0;
  78.     e = 1048576;
  79.   }
  80.   ~MY_WRITER(){
  81.     if(s){
  82.       fwrite_unlocked(buf, 1, s, stdout);
  83.     }
  84.   }
  85. }
  86. ;
  87. MY_WRITER MY_WRITER_VAR;
  88. void my_putchar_unlocked(int a){
  89.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  90.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  91.     MY_WRITER_VAR.s = 0;
  92.   }
  93.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  94. }
  95. inline void wt_L(char a){
  96.   my_putchar_unlocked(a);
  97. }
  98. inline void wt_L(long long x){
  99.   int s=0;
  100.   int m=0;
  101.   char f[20];
  102.   if(x<0){
  103.     m=1;
  104.     x=-x;
  105.   }
  106.   while(x){
  107.     f[s++]=x%10;
  108.     x/=10;
  109.   }
  110.   if(!s){
  111.     f[s++]=0;
  112.   }
  113.   if(m){
  114.     my_putchar_unlocked('-');
  115.   }
  116.   while(s--){
  117.     my_putchar_unlocked(f[s]+'0');
  118.   }
  119. }
  120. template<class T> inline T pow2_L(T a){
  121.   return a*a;
  122. }
  123. template<class S, class T> inline S chmin(S &a, T b){
  124.   if(a>b){
  125.     a=b;
  126.   }
  127.   return a;
  128. }
  129. template<class T, class S> void ZetaTransform_L(int N, T A[], S res[]){
  130.   int i;
  131.   int j;
  132.   int x;
  133.   int m;
  134.   for(j=(0);j<(N);j++){
  135.     res[j] = A[j];
  136.   }
  137.   for(i=1;i<N;i*=2){
  138.     for(j=(i);j<(N);j+=(2*i)){
  139.       m =min_L(N, j+i);
  140.       for(x=(j);x<(m);x++){
  141.         res[x] += res[x^i];
  142.       }
  143.     }
  144.   }
  145. }
  146. template<class T> void ZetaTransform_L(int N, T A[]){
  147.   int i;
  148.   int j;
  149.   int x;
  150.   int m;
  151.   for(i=1;i<N;i*=2){
  152.     for(j=(i);j<(N);j+=(2*i)){
  153.       m =min_L(N, j+i);
  154.       for(x=(j);x<(m);x++){
  155.         A[x] += A[x^i];
  156.       }
  157.     }
  158.   }
  159. }
  160. template<class T, class S> int subsetSum(int n, T a[], S res[]){
  161.   int i;
  162.   int k;
  163.   int sz = 1;
  164.   res[0] = 0;
  165.   for(k=(0);k<(n);k++){
  166.     for(i=(0);i<(sz);i++){
  167.       res[sz+i] = res[i] + a[k];
  168.     }
  169.     sz *= 2;
  170.   }
  171.   return sz;
  172. }
  173. int N;
  174. int M;
  175. long long R;
  176. long long X[200000];
  177. long long Y[200000];
  178. long long A[20];
  179. long long B[20];
  180. long long C[20];
  181. int ok[200000];
  182. int cnt[2000000];
  183. int zt[2000000];
  184. long long res[200000];
  185. long long cost[2000000];
  186. int main(){
  187.   int i, mask;
  188.   rd(N);
  189.   rd(M);
  190.   rd(R);
  191.   {
  192.     int Lj4PdHRW;
  193.     for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
  194.       rd(X[Lj4PdHRW]);
  195.       rd(Y[Lj4PdHRW]);
  196.     }
  197.   }
  198.   {
  199.     int e98WHCEY;
  200.     for(e98WHCEY=(0);e98WHCEY<(M);e98WHCEY++){
  201.       rd(A[e98WHCEY]);
  202.       rd(B[e98WHCEY]);
  203.       rd(C[e98WHCEY]);
  204.     }
  205.   }
  206.   R *= R;
  207.   for(i=(0);i<(N);i++){
  208.     int j;
  209.     for(j=(0);j<(M);j++){
  210.       if((pow2_L((X[i]-A[j])))+(pow2_L((Y[i]-B[j])))<= R ){
  211.         ok[i] |= (1<<j);
  212.       }
  213.     }
  214.   }
  215.   for(i=(0);i<(N);i++){
  216.     cnt[ok[i]]++;
  217.   }
  218.   ZetaTransform_L(1<<M, cnt, zt);
  219.   subsetSum(M, C, cost);
  220.   for(i=(0);i<(N);i++){
  221.     res[i] = 4611686016279904256LL;
  222.   }
  223.   for(mask=(0);mask<(1<<M);mask++){
  224.     i = N - zt[((1<<M)-1) ^ mask];
  225.     if(i==0){
  226.       continue;
  227.     }
  228.     chmin(res[i-1], cost[mask]);
  229.   }
  230.   for(i=(N)-1;i>=(1);i--){
  231.     chmin(res[i-1], res[i]);
  232.   }
  233.   for(i=(0);i<(N);i++){
  234.     if(res[i]==4611686016279904256LL){
  235.       res[i] = -1;
  236.     }
  237.   }
  238.   {
  239.     int ZIeRIny5;
  240.     for(ZIeRIny5=(0);ZIeRIny5<(N);ZIeRIny5++){
  241.       wt_L(res[ZIeRIny5]);
  242.       wt_L('\n');
  243.     }
  244.   }
  245.   return 0;
  246. }
  247. // cLay version 20201123-1
  248.  
  249. // --- original code ---
  250. // int N, M; ll R, X[2d5], Y[2d5], A[20], B[20], C[20];
  251. // int ok[2d5], cnt[2d6], zt[2d6];
  252. // ll res[2d5], cost[2d6];
  253. // {
  254. //   rd(N,M,R,(X,Y)(N),(A,B,C)(M));
  255. //   R *= R;
  256. //   rep(i,N) rep(j,M) if( (X[i]-A[j])**2 + (Y[i]-B[j])**2 <= R ) ok[i] |= (1<<j);
  257. //   rep(i,N) cnt[ok[i]]++;
  258. //   ZetaTransform(1<<M, cnt, zt);
  259. //   subsetSum(M, C, cost);
  260. // 
  261. //   rep(i,N) res[i] = ll_inf;
  262. //   rep(mask,1<<M){
  263. //     i = N - zt[((1<<M)-1) ^ mask];
  264. //     if(i==0) continue;
  265. //     res[i-1] <?= cost[mask];
  266. //   }
  267. // 
  268. //   rrep(i,1,N) res[i-1] <?= res[i];
  269. //   rep(i,N) if(res[i]==ll_inf) res[i] = -1;
  270. //   wtLn(res(N));
  271. // }
  272.  
Time limit exceeded #stdin #stdout 5s 4384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pwDDbZ
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!