fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long 
  3. #define f(i,n) for(int i=0;i<n;i++) 
  4. #define fr(i,a,b) for(int i=a;i<b;i++) 
  5. #define F first 
  6. #define S second 
  7. #define mp make_pair 
  8. #define pb push_back 
  9.  
  10. using namespace std;
  11.  
  12. int fun(vector<int> a) 
  13. { 
  14.  
  15. 	int size = a.size();
  16.     f(i,size)if(a[i]==0)a[i]=-1;
  17. 	int max_so_far = INT_MIN, max_ending_here = 0, 
  18.        start =0, end = 0, s=0; 
  19.  
  20.     for (int i=0; i< size; i++ ) 
  21.     { 
  22.         max_ending_here += a[i]; 
  23.  
  24.         if (max_so_far < max_ending_here) 
  25.         { 
  26.             max_so_far = max_ending_here; 
  27.             start = s; 
  28.             end = i; 
  29.         } 
  30.  
  31.         if (max_ending_here < 0) 
  32.         { 
  33.             max_ending_here = 0; 
  34.             s = i + 1; 
  35.         } 
  36.     } 
  37.     if(max_so_far>0){
  38.     	int sum = 0;
  39.     	f(i,size){
  40.     		if(i>=start and i<=end){
  41.     			if(a[i]==-1)sum++;
  42. 			}else{
  43. 				if(a[i]==1)sum++;
  44. 			}
  45. 		}
  46. 		return sum;
  47. 	}else
  48. 		return 0; 
  49. } 
  50.  
  51.  
  52.  
  53. void test(){
  54. 	ll n,k;
  55. 	cin>>n>>k;
  56. 	string s;
  57. 	cin>>s;
  58.  
  59. 	int total = 0;
  60. 	f(i,n){
  61. 		total = total + (s[i]-'0');
  62. 	}
  63. 	ll ans = n;
  64. 	int index = -1;
  65. 	for(int i=k-1;i>=0;i--){
  66. 		vector<int> v;
  67. 		int temp=0;
  68. 		for(int j=n-(k-i);j>=0;j=j-k){
  69. 			v.pb(s[j]-'0');
  70. 			temp = temp + (s[j]-'0');
  71. 		}
  72. 		ll cal = total-temp;
  73. 		cal = cal + fun(v);
  74. 		ans = min(ans,cal);
  75. 	}
  76.  
  77. 	cout<<ans<<"\n";
  78. }
  79.  
  80. int main(){ 
  81. 	std::ios::sync_with_stdio(false);
  82. 	cin.tie(0);
  83. 	cout.tie(0);
  84. 	int t=1;
  85. 	cin>>t;
  86. 	while(t--){
  87. 		test();
  88. 	}
  89. }
Success #stdin #stdout 0s 4164KB
comments (?)
stdin
copy 
6
9 2
010001010
9 3
111100000
7 4
1111111
10 3
1001110101
1 1
1
1 1
0
stdout
copy 
1
2
5
4
0
0
https://ideone.com/F5iCDW
language:
C++14 (gcc 8.3)
created:
4 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!