fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long;
  4.  
  5. const int inf=300000008;
  6. ll n,A[4][10003],f[16][10003],mina=-1e8,da=0;
  7.  
  8. void setup()
  9. {
  10.     for(int i=0;i<16;i++)
  11.         for(int j=0;j<10001;j++)
  12.             f[i][j]=-inf;
  13. }
  14. bool check(int mask)
  15. {
  16.     for(int i=1;i<4;i++)
  17.     {
  18.         int a=((mask&(1<<i))>0),
  19.         b=((mask&(1<<(i-1)))>0);
  20.         if(a && b)
  21.              return 0;
  22.     }
  23.     return 1;
  24. }
  25. bool ss(int A, int B)
  26. {
  27.     for(int i=0;i<4;i++)
  28.     {
  29.         if((A&(1<<i)))
  30.             if((B&(1<<i))) return 0;
  31.     }
  32.     return 1;
  33. }
  34. ll cal(int mask,int cot)
  35. {
  36.     ll ans=0;
  37.     for(int i=0;i<4;i++)
  38.     {
  39.         if((mask&(1<<i)))
  40.             ans+=A[i][cot];
  41.     }
  42.     return ans;
  43. }
  44. int main()
  45. {
  46.     setup();
  47.     cin>>n;
  48.     for(int i=0;i<4;i++)
  49.         for(int j=0;j<n;j++)
  50.         {
  51.             cin>>A[i][j];
  52.             if(A[i][j]<0)
  53.             {
  54.                 da++;
  55.                 mina=max(mina,A[i][j]);
  56.             }
  57.         }
  58.     if(da==4*n)
  59.     {
  60.         cout<<mina;
  61.         return 0;
  62.     }
  63.     for(int mask=0;mask<16;mask++)
  64.     {
  65.         if(check(mask))
  66.             f[mask][0]=cal(mask,0);
  67.     }
  68.     for(int j=1;j<n;j++)
  69.     {
  70.         for(int mask=0;mask<16;mask++)
  71.         {
  72.             if(!check(mask)) continue;
  73.             for(int M=0;M<16;M++)
  74.             {
  75.                 if(check(M))
  76.                 if(ss(mask,M))
  77.                 {
  78.                     f[mask][j]=
  79.                     max(f[mask][j],cal(mask,j)
  80.                         +f[M][j-1]);
  81.                 }
  82.             }
  83.         }
  84.     }
  85.     ll ans=0;
  86.     for(int mask=0;mask<16;mask++)
  87.         ans=max(ans,f[mask][n-1]);
  88.     cout<<ans;
  89. }
  90.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-100000000
https://ideone.com/MGT3px
QBSELECT_VNOI
language:
C++14 (clang 8.0)
created:
1 day 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!