Advertisement
madhukeshk3

Airplane Problem - Samsung R&D

Sep 5th, 2020
72
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int arr[15][5];
  5. int b[5][5];
  6.  
  7. const int INF=1e9;
  8.  
  9. void oprn(int row)
  10. {
  11.     for(int i=row;i>max(0,row-5);i--)
  12.     {
  13.         for(int j=0;j<5;j++)
  14.         {
  15.             if(arr[i][j]==2)
  16.             {
  17.                 b[row-i][j]=2;
  18.                 arr[i][j]=0;
  19.             }
  20.         }
  21.     }
  22. }
  23.  
  24. void revoprn(int row)
  25. {
  26.     for(int i=row;i>max(0,row-5);i--)
  27.     {
  28.         for(int j=0;j<5;j++)
  29.         {
  30.             if(b[row-i][j]==2)
  31.             {
  32.                 arr[i][j]=2;
  33.             }
  34.         }
  35.     }
  36. }
  37.  
  38. int rec(int pos,int coins,int row)
  39. {
  40.     if(pos<0||pos>4||coins<0)
  41.         return -INF;
  42.     if(arr[row][pos]==2)
  43.         coins-=1;
  44.     else if(arr[row][pos]==1)
  45.         coins+=1;
  46.  
  47.     if(row==0)
  48.         return coins;
  49.        
  50.     return max(rec(pos,coins,row-1),max(rec(pos-1,coins,row-1),rec(pos+1,coins,row-1)));
  51. }
  52.  
  53. void solve()
  54. {
  55.     int n;
  56.     cin>>n;
  57.  
  58.     for(int i=0;i<n;i++)
  59.         for(int j=0;j<5;j++)
  60.             cin>>arr[i][j];
  61.  
  62.     int mxcoin=-1;
  63.  
  64.     for(int i=n-1;i>3;i--)
  65.     {
  66.         oprn(i);
  67.  
  68.         int coins=max(rec(2,0,n-1),max(rec(1,0,n-1),rec(3,0,n-1)));
  69.         mxcoin=max(mxcoin,coins);
  70.         revoprn(i);
  71.     }
  72.  
  73.     cout<<mxcoin<<endl;
  74.  
  75.     return;
  76. }
  77.  
  78. int main()
  79. {
  80.     int t;
  81.     cin>>t;
  82.  
  83.     while(t--)
  84.         solve();
  85.  
  86.     return 0;
  87. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement