fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll suffix[2][1004];//this is used from ith index is there any cow left or not
  5. ll dp[1004][1004];
  6. ll check(vector<vector<ll>>&input,ll i)
  7. {
  8.     ll up=0,down=1,both=2;
  9.     if(input[0][i]==1 && input[1][i]==1){
  10.         return both;
  11.     }
  12.     if(input[0][i]==0 && input[1][i]==1){
  13.         return down;
  14.     }
  15.     return up;
  16. }
  17. ll recursion2(ll start,ll end,ll k,vector<vector<ll>>&input,vector<vector<pair<ll,ll>>>&axis)
  18. {
  19.     if(k<=0 && (suffix[0][start]>=1 || suffix[1][start]>=1)){
  20.         return 10000000008;//rectangle finish but cows left
  21.     }
  22.     if(k==0 && suffix[0][start]==0 && suffix[1][start]==0){
  23.         return 0;
  24.     }
  25.     if(start>end && k>0){
  26.         return 10000000008;//cows finish but rectangles remaining
  27.     }
  28.     if(dp[start][k]!=-1){
  29.         return dp[start][k];
  30.     }
  31.     ll Lup=-1,Ldown=-1,Rup,Rdown,anss=100000000000000;
  32.     for(ll i=start;i<=end;i++)
  33.     {
  34.         ll ss=check(input,i);
  35.         if(ss==0 && Lup==-1){Lup=i;Rup=i;}
  36.         if(ss==1 && Ldown==-1){Ldown=i;Rdown=i;}
  37.         if(ss==2){
  38.             if(Lup==-1){Lup=i;Rup=i;}
  39.             if(Ldown==-1){Ldown=i;Rdown=i;}
  40.         }
  41.         if(ss==0){
  42.             Rup=i;
  43.             if(Ldown!=-1){
  44.                 ll t,x;
  45.                 if(Lup<Ldown){t=Lup;x=0;
  46.                 }else{
  47.                     t=Ldown;x=1;
  48.                 }
  49.                 ll cost=2*(abs(axis[0][i].second-axis[x][t].second)+1);//Type C rectangle
  50.                 anss=min(anss,cost+recursion2(i+1,end,k-1,input,axis));
  51.                 cost=(abs(axis[1][Rdown].second-axis[1][Ldown].second)+1)+(abs(axis[0][Rup].second-axis[0][Lup].second)+1);
  52.                 anss=min(anss,cost+recursion2(i+1,end,k-2,input,axis));//Combination of Type A and B rectangle till ith index
  53.             }
  54.             else{
  55.                 ll cost=(axis[0][i].second-axis[0][Lup].second+1);
  56.                 anss=min(anss,cost+recursion2(i+1,end,k-1,input,axis));//only Type A rectangle
  57.             }
  58.         }
  59.         if(ss==1){
  60.             Rdown=i;
  61.             if(Lup!=-1){ll t,x;
  62.                 if(Lup<Ldown){t=Lup;x=0;
  63.                 }else{t=Ldown;x=1;
  64.                 }
  65.                 ll cost=2*(abs(axis[1][i].second-axis[x][t].second)+1);
  66.                 anss=min(anss,cost+recursion2(i+1,end,k-1,input,axis));//Type C rectangle
  67.                 cost=(abs(axis[1][Rdown].second-axis[1][Ldown].second)+1)+(abs(axis[0][Rup].second-axis[0][Lup].second)+1);
  68.                 anss=min(anss,cost+recursion2(i+1,end,k-2,input,axis)); //Combination of Type A and B rectangle till ith index
  69.             }
  70.             else{
  71.                 ll cost=(abs(axis[1][i].second-axis[1][Ldown].second)+1);
  72.                 anss=min(anss,cost+recursion2(i+1,end,k-1,input,axis));//only Type B rectangle
  73.             }
  74.         }
  75.         if(ss==2){
  76.             Rup=i;Rdown=i;
  77.             ll t,x;
  78.             if(Lup<Ldown){
  79.                 t=Lup;x=0;
  80.             }else{
  81.                 t=Ldown;x=1;
  82.             }
  83.             ll cost=2*(abs(axis[1][i].second-axis[x][t].second)+1);
  84.             anss=min(anss,cost+recursion2(i+1,end,k-1,input,axis));//Type C rectangle
  85.         }
  86.     }
  87.     return dp[start][k]=anss;
  88. }
  89. void solve()
  90. {
  91.     ll n,k,b;
  92.     cin>>n>>k>>b;
  93.     vector<pair<ll,ll>>abc,def,mix;
  94.     for(ll i=0,u,v;i<n;++i){
  95.         cin>>u>>v;
  96.         if(u==1){
  97.             abc.push_back({u,v});
  98.         }else{
  99.             def.push_back({u,v});
  100.         }
  101.         mix.push_back({u,v});
  102.     }
  103.     sort(abc.begin(),abc.end());sort(def.begin(),def.end());
  104.     sort(mix.begin(),mix.end(),[](pair<ll,ll>&aa,pair<ll,ll>&bb){
  105.         if(aa.second==bb.second){return aa.first<bb.first;}
  106.         return aa.second<bb.second;
  107.     });
  108.     ll col=1,prev=mix[0].second;
  109.     for(ll i=1;i<mix.size();++i){
  110.         if(mix[i].second!=prev){
  111.             col++;
  112.         }
  113.         prev=mix[i].second;
  114.     }
  115.     vector<vector<ll>>input(2,vector<ll>(col));
  116.     vector<vector<pair<ll,ll>>>axis(2,vector<pair<ll,ll>>(col));
  117.     for(ll i=0,j=0;i<mix.size();++i){
  118.         if(i+1<mix.size()){
  119.             if(mix[i].second==mix[i+1].second){
  120.                 input[0][j]=1;input[1][j]=1;
  121.                 axis[0][j]={1,mix[i].second};
  122.                 axis[1][j]={2,mix[i].second};
  123.                 i++;j++;
  124.                 continue;
  125.             }
  126.         }
  127.         if(mix[i].first==1){
  128.             input[0][j]=1;
  129.             axis[0][j]={1,mix[i].second};
  130.             j++;
  131.         }
  132.         else{
  133.             axis[1][j]={2,mix[i].second};
  134.             input[1][j]=1;j++;
  135.         }
  136.         for(ll i=0;i<2;++i)//calculating suffix sum from right to left
  137.         {
  138.             for(ll j=col-1;j>=0;--j){
  139.                 if(input[i][j]==1){
  140.                     suffix[i][j]=1+suffix[i][j+1];
  141.                 }
  142.                 else{
  143.                     suffix[i][j]=suffix[i][j+1];
  144.                 }
  145.             }
  146.         }
  147.     }
  148.     memset(dp,-1,sizeof(dp));cout<<recursion2(0,col-1,k,input,axis)<<endl;
  149.     memset(suffix, 0, sizeof(suffix));
  150. }
  151.  
  152. int main()
  153. {
  154.     int t=1;
  155.     cin >> t;
  156.     while (t--)
  157.     {
  158.         solve();
  159.     }
  160.     return 0;
  161. }
Success #stdin #stdout 0s 11184KB
comments (?)
stdin 
1
8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4
stdout 
10
https://ideone.com/mJXOR8
language:
C++ (gcc 8.3)
created:
5 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!