fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define MOD 1000000007
  5. #define Bit(mask , i) ((mask >> i) & 1)
  6.  
  7. const int N = 9;
  8. int n;
  9. int check[1 << N];
  10. long long f[10005][1 << N] , a[N][10007];
  11.  
  12. void inp(){
  13. 	cin >> n;
  14. 	for (int i=0 ; i<8 ; i++){
  15. 		for (int j=0 ; j<n ; j++){
  16. 			cin >> a[i][j];
  17. 		}
  18. 	}
  19. }
  20.  
  21. void solve(){
  22. 	long long ans = -1e15;
  23. 	for (int mask=0 ; mask<255 ; mask++){
  24. 		bool bl = 1;
  25. 		for (int i=0 ; i<7 ; i++){
  26. 			if (!Bit(mask , i)) continue;
  27. 			if (Bit(mask , i + 1)){
  28. 				bl = 0;
  29. 				break;
  30. 			}
  31. 		}
  32. 		if (bl){
  33. 			check[mask] = 1;
  34. 			long long val = 0;
  35. 			for (int i=0 ; i<8 ; i++){
  36. 				if (Bit(mask , i)) val += a[i][0];
  37. 			}
  38. 			f[0][mask] = val;
  39. 			ans = max(ans , f[0][mask]);
  40. 		} 
  41. 	}
  42. 	for (int i=1 ; i<n ; i++){
  43. 		for (int mask=0 ; mask<(1 << 8) ; mask++){
  44. 			if (!check[mask]) continue;
  45. 			f[i][mask] = -1e12;
  46. 			long long val = 0;
  47. 			for (int j=0 ; j<8 ; j++)
  48. 			 	if (Bit(mask , j)) val += a[j][i];
  49. 			for (int _mask=0 ; _mask<(1 << 8) ; _mask++){
  50. 				if (!check[_mask]) continue;
  51. 				if ((mask & _mask) != 0) continue;
  52. 				f[i][mask] = max(f[i][mask] , val + f[i - 1][_mask]);
  53. 			}
  54. 			ans = max(ans , f[i][mask]);
  55. 		}
  56. 	}
  57. 	cout << ans;
  58. }
  59.  
  60. int main(){
  61. //	freopen("xhmax.inp" , "r" , stdin);
  62. //	freopen("xhmax.out" , "w" , stdout);
  63.     faster;
  64.     inp();
  65.     solve();
  66.     return 0;
  67. }
  68. // cnlk
  69.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0zg4Yt
language:
C++14 (gcc 8.3)
created:
2 days 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!