fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll dp[1002][102][2],black[1000],white[1000],mins[2],maxs[2],n;
  5. ll recurse(int state,int pos,int len)
  6. {
  7.      //cout<<state<<" s "<<pos<<" p "<<endl;
  8.      if(pos>=n && len<mins[state])
  9.      {
  10.      	// cout<<state<<" "<<len<<" left"<<endl;
  11.      return INT_MAX;}
  12.      else if(pos>=n)
  13.      {
  14.      	// cout<<state<<" "<<len<<endl;
  15.      return 0;}
  16.      if(dp[pos][len][state]!=-1)
  17.      return dp[pos][len][state];
  18.      ll temp=INT_MAX;
  19.      ll temp2,temp3;
  20.      temp2=(state==0?white[pos]:black[pos]);
  21.      temp3=(state==1?white[pos]:black[pos]);
  22.      if(len<mins[state])
  23.      temp=min(temp,temp2+recurse(state,pos+1,len+1));
  24.      else if(len>=maxs[state])
  25.      temp=min(temp,temp3+recurse(!state,pos+1,1));
  26.      else{
  27.      	if(state==0)
  28.      	temp=min(white[pos]+recurse(state,pos+1,len+1),black[pos]+recurse(!state,pos+1,1));
  29.      	else temp=min(white[pos]+recurse(!state,pos+1,1),black[pos]+recurse(state,pos+1,len+1));
  30.      }
  31.      dp[pos][len][state]=temp;
  32.      return temp;
  33. }
  34. int main() {
  35.  
  36. 	int t;
  37. 	cin>>t;
  38. 	while(t--)
  39. 	{
  40. 	    cin>>n;
  41. 	    memset(dp,-1,sizeof(dp));
  42. 	    memset(black,0,sizeof(black));
  43. 	    memset(white,0,sizeof(white));
  44. 	    for(int i=0;i<50;i++)
  45. 	    {
  46. 	        for(int j=0;j<n;j++)
  47. 	        {
  48. 	            ll temp;
  49. 	            cin>>temp;
  50. 	            if(temp)
  51. 	            white[j]++;
  52. 	            else black[j]++;
  53. 	        }
  54. 	    }
  55.  
  56. 	    /*for(int i=0;i<n;i++)
  57. 	    {
  58. 	    	cout<<white[i]<<" "<<black[i]<<endl;
  59. 	    }*/
  60. 	    cin>>mins[0]>>maxs[0];
  61. 	    cin>>mins[1]>>maxs[1];
  62. 	    ll ans=white[0]+recurse(0,1,1);
  63. 	    ans=min(ans,black[0]+recurse(1,1,1));
  64. 	    if(ans>=INT_MAX)
  65. 	    cout<<-1<<endl;
  66. 	    else cout<<ans<<endl;
  67. 	}
  68.  
  69. 	return 0;
  70. }
Success #stdin #stdout 0s 4708KB
comments (?)
stdin
copy 
1
5
1 1 1 1 0
3 5
3 4
stdout
copy 
101
https://ideone.com/W4KqEg
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!