fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. ifstream fi("select.inp");
  5. ofstream fo("select.out");
  6.  
  7. int n;
  8. int d[16], f[16][100000], res = -3e8;
  9. int a[4][100000];
  10.  
  11. void inp(){
  12. 	ios::sync_with_stdio(false);
  13. 	cin.tie(0);
  14. 	cin >> n;
  15.     for (int i = 0; i < 4; i++)
  16.         for (int j = 1; j <= n; j++){
  17.             cin >> a[i][j]; 
  18. 			res = max(res, a[i][j]);      
  19.         }
  20. }
  21.  
  22. int xlbit(int n, int i){
  23. 	return n & (1 << i);
  24. }
  25.  
  26. void checkbtcs(){
  27. 	for(int i  = 0; i < (1 << 4); i++){
  28. 		bool tmp = 1;
  29. 		for(int j = 0; j < 3; j++){
  30. 			if(xlbit(i, j) && xlbit(i, j + 1)) tmp = 0;
  31. 			d[i] = tmp;
  32. 		}
  33. 	}
  34. }
  35.  
  36. void qhdtt(){
  37. 	for(int i = 1; i <= n; i++){
  38. 		for(int bit = 0; bit < (1 << 4); bit++)
  39. 			if(d[bit]){
  40. 				int sum = 0, ans = 0;
  41. 				for(int k = 0; k < 4; k++)
  42. 					if(xlbit(bit, k))
  43. 						sum += a[k][i];
  44. 				for (int k = 0;k < (1 << 4); k++)
  45.             		if (d[k] && ((k & bit) == 0))
  46.                 		ans= max(f[k][i-1] + sum, ans);
  47.        			f[bit][i] = ans;
  48. 			}
  49. 	}
  50. }
  51.  
  52. void out(){
  53.     int ans =0;
  54.     for (int i = 0;i < (1 << 4); i++)
  55.         ans = max(ans, f[i][n]);
  56.     if (ans) cout<<ans;
  57.     else cout <<res;
  58. }
  59.  
  60. int main(){
  61. 	inp();
  62. 	checkbtcs();
  63. 	memset(f, -(1 << 18), sizeof f);
  64. 	qhdtt();
  65. 	out();
  66. 	return 0;
  67. }
  68. /*
  69. 3
  70. -1 9 3
  71. -4 5 -6
  72. 7 8 9
  73. 9 7 2
  74. */
  75.  
Success #stdin #stdout 0.01s 10848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-300000000
https://ideone.com/bDWUly
language:
C++ (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!