fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define loop(i,a,b) for(int i=a;i<b;i++)
  3. #define loopb(i,a,b) for(int i=a;i>=b;i--)
  4. #define loopm(i,a,b,step) for(int i=a;i<b;i+=step)
  5. #define loopbm(i,a,b,step) for(int i=a;i>=b;i-=step)
  6. #define pb(a) push_back(a)
  7. #define mp(a,b) make_pair(a,b)
  8. #define init(arr,val) memset(arr,val,sizeof(arr))
  9. #define INF 1000000007
  10. #define MOD 1000000007
  11. #define BINF 1000000000000000001
  12. #define int long long int
  13. #define double long double
  14.  
  15. using namespace std;
  16.  
  17. int grid[1005][55];
  18. int w,x,y,z;
  19. int dp[1005][105][2];
  20.  
  21.  
  22. int go(int n,int curr,int flag)
  23. {
  24. 	if(n<0)
  25. 	{
  26. 		if(flag==0)
  27. 		{
  28. 			//white
  29. 			if(curr<y) return INT_MAX;
  30. 			else return 0;
  31. 		}
  32. 		else
  33. 		{
  34. 			//black
  35. 			if(curr<w) return INT_MAX;
  36. 			else return 0;
  37. 		}
  38. 	}
  39. 	else if(dp[n][curr][flag]>0) return dp[n][curr][flag];
  40.  
  41. 	else
  42. 	{
  43. 		int ans=0;
  44. 		if(flag==0)
  45. 		{
  46. 			//white
  47. 			if(curr<y)
  48. 			{
  49. 				int cost=0;
  50. 				loop(i,0,50)
  51. 				{
  52. 					if(grid[n][i]==1) cost++;
  53. 				}
  54. 				ans=go(n-1,curr+1,0)+cost;
  55. 			}
  56. 			else if(curr==z)
  57. 			{
  58. 				int cost=0;
  59. 				loop(i,0,50) 
  60. 				{
  61. 					if(grid[n][i]==0) cost++;
  62. 				}
  63.  
  64. 				ans=go(n-1,1,1)+cost;
  65. 			}
  66. 			else
  67. 			{
  68. 				int cost=0;
  69. 				loop(i,0,50)
  70. 				{
  71. 					if(grid[n][i]==1) cost++;
  72. 				}
  73. 				ans=go(n-1,curr+1,0)+cost;
  74.  
  75. 				cost=0;
  76. 				loop(i,0,50)
  77. 				{
  78. 					if(grid[n][i]==0) cost++;
  79. 				}
  80. 				ans=min(ans,go(n-1,1,1)+cost);
  81. 			}
  82. 		}
  83. 		else
  84. 		{
  85. 			if(curr<w)
  86. 			{
  87. 				int cost=0;
  88. 				loop(i,0,50)
  89. 				{
  90. 					if(grid[n][i]==0) cost++;
  91. 				}
  92. 				ans=go(n-1,curr+1,1)+cost;
  93. 			}
  94. 			else if(curr==x)
  95. 			{
  96. 				int cost=0;
  97. 				loop(i,0,50) 
  98. 				{
  99. 					if(grid[n][i]==1) cost++;
  100. 				}
  101.  
  102. 				ans=go(n-1,1,0)+cost;
  103. 			}
  104. 			else
  105. 			{
  106. 				int cost=0;
  107. 				loop(i,0,50)
  108. 				{
  109. 					if(grid[n][i]==0) cost++;
  110. 				}
  111. 				ans=go(n-1,curr+1,1)+cost;
  112.  
  113. 				cost=0;
  114. 				loop(i,0,50)
  115. 				{
  116. 					if(grid[n][i]==1) cost++;
  117. 				}
  118. 				ans=min(ans,go(n-1,1,0)+cost);
  119. 			}
  120. 		}
  121.  
  122. 		dp[n][curr][flag]=ans;
  123. 		return ans;
  124. 	}
  125. }
  126.  
  127. #undef int
  128. int main()
  129. {
  130. #define int long long int
  131.     ios_base::sync_with_stdio(false);
  132.     cin.tie(NULL);
  133.     cout.tie(NULL);
  134.     //freopen("input.txt","r",stdin);
  135.     int t;
  136.     cin>>t;
  137.     while(t--)
  138.     {
  139.     	loop(i,0,1005)
  140.     	{
  141.     		loop(j,0,55) grid[i][j]=0;
  142.     		loop(j,0,105) loop(k,0,2) dp[i][j][k]=0;
  143.     	}
  144.  
  145.     	int n;
  146.     	cin>>n;
  147.     	loop(i,0,50)
  148.     	{
  149.     		loop(j,0,n) cin>>grid[j][i];
  150.     	}
  151.  
  152.     	cin>>w>>x;
  153.     	cin>>y>>z;
  154.  
  155.     	int ans=0;
  156.     	int cost=0;
  157.     	loop(i,0,50) if(grid[n-1][i]==0) cost++;
  158.     	ans=go(n-2,1,1)+cost;
  159.     	cost=0;
  160.     	loop(i,0,50) if(grid[n-1][i]==1) cost++;
  161.     	ans=min(ans,go(n-2,1,0)+cost);
  162.  
  163.     	if(ans>=INT_MAX) cout<<-1<<endl;
  164.     	else cout<<ans<<endl;
  165.     }
  166.  
  167.     return 0;
  168. }
Success #stdin #stdout 0s 5180KB
comments (?)
stdin
copy 
1
3
0 0 1
0 0 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 0
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 0 1
0 0 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 0
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 0 1
0 0 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 0
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
1 3
1 2
stdout
copy 
9
https://ideone.com/tps2RO
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!