fork(2) download
copy 
  1. #pragma GCC optimize("O3")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long int
  5. #define llu unsigned long long int
  6. #define max3(a,b,c) max(a,max(b,c))
  7. double PI=acos(-1.0);
  8. ll ans22=0;
  9. int dp[1005][1005][2];
  10. int x,y;
  11. int n;
  12. vector<int> a(1005);
  13. vector<int> b(1005);
  14. // dp denotes what is the minimum cost to transform the array a starting 
  15. // at "index" with last 0 or 1 placed at "lindex" uptil "index-1"
  16. // ie if we have transform array like 1 1 1 0 0 0 0
  17. // we are at index 7 (0 indexing) then our dp state will be like dp(7,3,0) ie we placed 0 from index 3-6
  18. int fun(int index,int lindex,int f)
  19. {
  20. 	if(index==n)
  21. 	{
  22. 		if(n-lindex>=x && n-lindex<=y)return 0;
  23. 		else return 1e8;
  24. 	}
  25.  
  26. 	int &res=dp[index][lindex][f];
  27. 	if(res!=-1)
  28. 		return res;
  29.     res=1e8;
  30.  
  31. 	if(f==0){
  32. 		int cost=(a[index]==0)?0:b[index];    //placing 0 at "index" and check if we need to flip or not,if yes cost=b[index]
  33. 		int pos1=index-lindex+1;              //we calculated the size of subarray ending at "index" which contains only 0
  34. 		if(pos1>=x && pos1<=y)res=min(res,cost+fun(index+1,lindex,0));//if size of this subarray fits the criteria we can put 0 at this index
  35.  
  36.         pos1=index-lindex;                    //we calculated the size of subarray ending at "index-1" which contains only 0
  37. 		cost=(a[index]==1)?0:b[index];       //placing 1 at "index" and check if we need to flip or not,if yes cost=b[index]
  38.  
  39. 		if(pos1>=x && pos1<=y)
  40. 		res=min(res,cost+fun(index+1,index,1));//if size of this subarray fits the criteria we can put 1 at this index
  41. 	}else{//same as above 
  42. 		int cost=(a[index]==0)?0:b[index];
  43. 		int pos1=index-lindex;                 //we calculated the size of subarray ending at "index-1" which contains only 1
  44. 		if(pos1>=x && pos1<=y)
  45. 		res=min(res,cost+fun(index+1,index,0));//if size of this subarray fits the criteria we can put 0 at this index
  46.  
  47. 		pos1=index-lindex+1;                   //we calculated the size of subarray ending at "index" which contains only 1
  48. 		cost=(a[index]==1)?0:b[index];              
  49. 		if(pos1>=x && pos1<=y)res=min(res,cost+fun(index+1,lindex,1));//placing 1 after checking criteria
  50. 	}
  51.  
  52. 	return res;
  53.  
  54. }
  55.  
  56.  
  57. int main()
  58. {
  59. 	int t;
  60. 	scanf("%d",&t);
  61. 	while(t--)
  62. 	{
  63. 		scanf("%d",&n);                      //input n
  64. 		scanf("%d%d",&x,&y);                 //input x y
  65. 		for(int i=0;i<n;i++)
  66. 			scanf("%d",&a[i]);               //input A 
  67. 		for(int i=0;i<n;i++)
  68. 			scanf("%d",&b[i]);              //input B
  69. 		memset(dp,-1,sizeof dp);
  70.  
  71. 		int ans=1e8;
  72.  
  73. 		int cost=(a[0]==0)?0:b[0];          //placing 0 at first index and check if we need to flip or not,if yes cost=b[0]
  74. 		ans=min(ans,cost+fun(1,0,0));
  75.  
  76. 		cost=(a[0]==1)?0:b[0];              //placing 1 at first index and check if we need to flip or not,if yes cost=b[0]
  77. 		ans=min(ans,cost+fun(1,0,1));
  78.  
  79. 		printf("%d\n",ans);
  80. 	}
  81.  
  82. 	return 0;
  83. }
Success #stdin #stdout 0s 23128KB
comments (?)
stdin
copy 
1
5
2 3
0 1 0 1 0
10 5 11 4 1
stdout
copy 
6
https://ideone.com/lcUUTo
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!