fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Aggressive cows
  5. struct cowpp
  6. {
  7.     int profit;
  8.     int position;
  9. };
  10.  
  11. map<string,cowpp> m;
  12.  
  13. cowpp LargestMinimumDistance(int c,vector<int> v,int l,int r)
  14. {
  15.  
  16.     string key = to_string(c+l+r);
  17.     if(m.find(key)!=m.end())
  18.     {
  19.         return m[key];
  20.     }
  21.  
  22.     cowpp result;
  23.     if(l>=r||c<2)
  24.     {
  25. //        cout<<"As per question, this block shouldn't get executed\n";
  26.         result.profit=0;
  27.         result.position=0;
  28.         m[key]=result;
  29.         return m[key];
  30.     }
  31.  
  32.     if(c==2)
  33.     {
  34.         result.profit=v[r]-v[l];
  35.         result.position=l;
  36. //        cout<<"27...."<<result.profit<<"\n";
  37.         m[key]=result;
  38.         return m[key];
  39.     }
  40.  
  41.     if(r-l+1==c)
  42.     {
  43.         result.position = l;
  44.         result.profit = INT_MAX;
  45.         for(int i=l;i<r;i++)
  46.         {
  47.             if(result.profit>(v[i+1]-v[i]))
  48.             {
  49.                 result.position=i;
  50.                 result.profit = (v[i+1]-v[i]);
  51.             }
  52.         }
  53. //        cout<<"43...."<<result.profit<<"\n";
  54.         m[key]=result;
  55.         return m[key];
  56.     }
  57.  
  58.     result.profit = INT_MIN;
  59.     result.position = l;
  60.     for(int i=l;i<=l+(r-c+1);i++)
  61.     {
  62. //        cout<<"for range "<<l<<", "<<l+(r-c+1)<<"\n";
  63. //        cout<<"now i is "<<i<<"\n";
  64.         for(int j=i+1;j<=(i+1)+r-c+1;j++){
  65.             cowpp temp = LargestMinimumDistance(c-1,v,j,r);
  66. //        cout<<"temp position is "<<temp.position<<"\n";
  67. //        cout<<"temp profit is "<<temp.profit<<"\n";
  68.             int profit = min(v[temp.position]-v[i],temp.profit);
  69. //        cout<<"now profit for i with "<<i<<" and range "<<l<<", "<<l+(r-c+1)<<" is "<<profit<<"\n";
  70.             if(result.profit<profit)
  71.             {
  72.                 result.profit = profit;
  73.                 result.position=i;
  74.             }
  75.         }
  76.     }
  77.     m[key]=result;
  78.     return m[key];
  79. }
  80.  
  81. int main()
  82. {
  83.     int t;
  84.     cin>>t;
  85.     while(t--)
  86.     {
  87.         int n,c;
  88.         cin>>n>>c;
  89.         vector<int> v;
  90.         for(int i=0;i<n;i++)
  91.         {
  92.             int a;
  93.             cin>>a;
  94.             v.push_back(a);
  95.         }
  96.         sort(v.begin(),v.end());
  97.         vector<int>::iterator it;
  98.         cowpp result = LargestMinimumDistance(c,v,0,n-1);
  99.         cout<<result.profit<<"\n";
  100.     }
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
1
5 3
1 2 3 55 100
stdout
copy 
45
https://ideone.com/1IC8BL
language:
C++ (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!