fork download
copy 
  1. #include<iostream>
  2. using namespace std;
  3. using ll = long long;
  4. #define maxn 10005
  5. int n,a[5][maxn],dp[maxn][16],res=-1e9;
  6. void input()
  7. {
  8. 	cin>>n;
  9. 	for (int i=1;i<=4;i++)
  10. 		for (int j=1;j<=n;j++)
  11. 		{
  12. 			cin>>a[i][j];
  13. 			res=max(res,a[i][j]);
  14. 		}
  15. }
  16. int check(int x)
  17. {
  18. 	if (x==3 || x==6 || x==7 || x>=11) return 0;
  19. 	return 1;
  20. }
  21. int get_val(int i,int x)
  22. {
  23. 	int sum=0;	
  24. 	for (int j=0;j<4;j++)
  25. 		if ((x>>j)&1) sum+=a[j+1][i];
  26. 	return sum;
  27. }
  28. void process()
  29. {
  30. 	if (res<=0)
  31. 	{
  32. 		cout<<res;
  33. 		return;
  34. 	}
  35. 	for (int i=1;i<=n;i++)
  36. 		for (int x=0;x<16;x++)
  37. 			if (check(x))
  38. 			{
  39. 				int T=get_val(i,x);
  40. 				dp[i][x]=-1e9;
  41. 				for (int z=0;z<16;z++)
  42. 					if (check(z) && (x&z)==0) dp[i][x]=max(dp[i][x],dp[i-1][z]+T);
  43. 			}
  44. 	for (int i=0;i<16;i++) 
  45. 		if (check(i)) res=max(res,dp[n][i]);
  46. 	cout<<res;
  47. }
  48. int main()
  49. {
  50. 	// freopen("thu.inp","r",stdin);
  51. 	ios_base::sync_with_stdio(0);
  52. 	cin.tie(NULL);
  53. 	input();
  54. 	process();
  55. }
  56.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
-1 9 3
-4 5 -6
7 8 9
9 7 2
stdout
copy 
32
https://ideone.com/u6StPT
language:
C++ (gcc 8.3)
created:
3 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!