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