fork(4) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long int ll;
  6. ll pts[100005][6]={0};
  7.  
  8. ll mnht(ll pt[100005][6], int kth, int idx, int d)
  9. {
  10.     ll dist=0;
  11.  
  12.     for(int i=0;i<d;i++)
  13.     {
  14.         dist+=abs(pt[kth][i]-pt[idx][i]);
  15.     }
  16.  
  17.     return dist;
  18. }
  19.    /*
  20.    10
  21.    -70 -64 -6 -56 64 61 -57 16 48 -98
  22.    */
  23. ll max_cmb(ll cmbn[6], ll pt[100005][6], int n, int d)
  24. {
  25.     ll pk=0;ll idx=0;
  26.  
  27.    for(int i=0;i<n;i++)
  28.    {
  29.        ll val=0;
  30.  
  31.        for(int j=0;j<d;j++)
  32.        {
  33.            val+=(1-2*cmbn[j])*pt[i][j];
  34.        }
  35.  
  36.        if(val>pk)
  37.        {
  38.            pk=val;
  39.            idx=i;
  40.        }
  41.    }
  42.  
  43.    return idx;
  44. }
  45.  
  46. int main()
  47. {
  48.    int n, d;
  49.    cin>>n>>d;
  50.  
  51.    for(int i=0;i<n;i++)
  52.    {
  53.        for(int j=0;j<d;j++)
  54.         cin>>pts[i][j];
  55.    }
  56.  
  57.    ll pk[2<<d];
  58.  
  59.    for(int j=0;j< 1<<(d);j++)
  60.    {
  61.        ll cmbn[6]={0};
  62.        for(int dig=0;dig< d; dig++)
  63.        {
  64.            if(j & 1<<dig)
  65.              cmbn[dig]=1;
  66.           // cout<<cmbn[dig]<<" ";
  67.        }
  68. //cout<<endl;
  69.        pk[j]=max_cmb(cmbn, pts, n, d);
  70.    }
  71.  
  72.    ll maxd=0;
  73.    for(int i=0;i<n;i++)
  74.    {
  75.        for(int j=0;j< 1<<(d);j++)
  76.        maxd=max(maxd, mnht(pts, i, pk[j], d));
  77.    }
  78.  
  79.    cout<<maxd<<endl;
  80.    return 0;
  81. }
  82.  
Time limit exceeded #stdin #stdout 5s 19928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/obsrth
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!