fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     ios_base::sync_with_stdio(0);
  6.     cin.tie(0);
  7.     cout.tie(0);
  8.     int t;
  9.     cin>>t;
  10.     while(t--){
  11.     	int n,k;
  12.     	cin>>n>>k;
  13.         string s;
  14.         cin>>s;
  15.         int sum[n];
  16.         for(int i=0;i<n;i++){
  17. 			int c;
  18. 			if(s[i]=='1')
  19. 				c=1;
  20. 			else
  21. 				c=0;
  22. 			if(i==0){
  23. 				sum[i]=c;
  24. 			}
  25. 			else
  26. 				sum[i] = sum[i-1] +c;
  27. 		}
  28. 		//for(int i=0;i<n;i++)
  29. 		//	cout<<sum[i]<<" ";
  30. 		int ans=0;
  31. 		int i=0;
  32. 		while(i<n){
  33. 			int start = i;
  34. 			int end = upper_bound(sum+i,sum+n,sum[start])-sum;
  35. 			int zero ;
  36. 			if(start==0 and s[start]=='0'){
  37. 				zero = end-start;
  38. 			}
  39. 			else{
  40. 				zero=end-start-1;
  41. 			}
  42.  
  43. 			//cout<<start<<" "<<end<<" ";
  44.  
  45. 			//cout<<zero<<" ";
  46.  
  47. 			if(start==0 and end==n){
  48. 				if(zero>0){
  49. 					ans+= zero/(k+1);
  50. 				zero%=(k+1);
  51. 				if(zero%(k+1)!=0 and zero>0)
  52. 					ans+=1;
  53. 				}
  54. 			}
  55. 			else if(start==0 and end<=n-1){
  56. 				zero-=k;
  57. 			//	cout<<zero<<" ";
  58. 				if(zero>0){
  59. 					ans+= zero/(k+1);
  60. 				zero%=(k+1);
  61. 				//cout<<zero<<" ";
  62. 				if(zero%(k+1)!=0 and zero>0)
  63. 					ans+=1;
  64. 				}
  65. 			//	cout<<ans<<" ";
  66. 			}
  67. 			else if(start>0 and end<=n-1){
  68. 			//	cout<<"case3 ";
  69. 				zero-=k;
  70. 				zero-=k;
  71. 			//	cout<<zero<<" ";
  72. 				if(zero>0){
  73. 					ans+= zero/(k+1);
  74. 				zero%=(k+1);
  75. 				if(zero%(k+1)!=0 and zero>0)
  76. 					ans+=1;
  77. 				}
  78.  
  79. 			//	cout<<ans<<" ";
  80. 			}
  81. 			else if(start>0 and end==n){
  82. 			//	cout<<"case4 ";
  83. 				zero-=k;
  84. 			//	cout<<zero<<" ";
  85. 				if(zero>0){
  86. 					ans+= zero/(k+1);
  87. 				zero%=(k+1);
  88. 				if(zero%(k+1)!=0 and zero>0)
  89. 					ans+=1;
  90. 				}
  91. 			//	cout<<ans<<" ";
  92. 			}
  93. 			//cout<<ans<<" ";
  94. 			i = end;
  95. 		}
  96. 		cout<<ans<<"\n";
  97. 		//cout<<"\nFinal ans: "<<ans;
  98. 	}
  99. }
  100.  
  101.  
Runtime error #stdin #stdout 0s 4512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Dt76cw
language:
C++ (gcc 8.3)
created:
3 years 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!