fork download
  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. if(pos>=n && len<mins[state])
  8. return INT_MAX;
  9. if(pos>=n)
  10. return 0;
  11. if(len>=maxs[state])
  12. return INT_MAX;
  13. if(dp[pos][len][state]!=-1)
  14. return dp[pos][len][state];
  15. ll temp=INT_MAX,temp1;
  16. if(state==0)
  17. {
  18. temp1=white[pos];
  19. }
  20. else{
  21. temp1=black[pos];
  22. }
  23. len++;
  24. if(len>=mins[state] & pos!=n-1)
  25. temp=min(temp,temp1+recurse(!state,pos+1,0));
  26. temp=min(temp,temp1+recurse(state,pos+1,len));
  27. len--;
  28. dp[pos][len][state]=temp;
  29. return temp;
  30. }
  31. int main() {
  32.  
  33. int t;
  34. cin>>t;
  35. while(t--)
  36. {
  37. cin>>n;
  38. memset(dp,-1,sizeof(dp));
  39. memset(black,0,sizeof(black));
  40. memset(white,0,sizeof(white));
  41. for(int i=0;i<50;i++)
  42. {
  43. for(int j=0;j<n;j++)
  44. {
  45. ll temp;
  46. cin>>temp;
  47. if(temp)
  48. white[j]++;
  49. else black[j]++;
  50. }
  51. }
  52. /*for(int i=0;i<n;i++)
  53. {
  54. cout<<white[i]<<" "<<black[i]<<endl;
  55. }*/
  56. cin>>mins[0]>>maxs[0];
  57. cin>>mins[1]>>maxs[1];
  58. ll ans=min(recurse(0,0,0),recurse(1,0,0));
  59. if(ans>=INT_MAX)
  60. cout<<-1<<endl;
  61. else cout<<ans<<endl;
  62. }
  63.  
  64. return 0;
  65. }
Success #stdin #stdout 0s 4772KB
stdin
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
9