fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5.  
  6.  
  7. const int M = 1000000007;
  8. const int N = 3e5+9;
  9. const int INF = 2e9+1;
  10. const int MAXN = 100000;
  11. const int LINF = 2000000000000000001;
  12.  
  13. //_ ***************************** START Below *******************************
  14.  
  15.  
  16.  
  17. vector<int> a;
  18.  
  19.  
  20. //* Template1 for Atmost k (i.e. <= k )
  21.  
  22. void consistency1(int n, int k){
  23.  
  24. 	int s = 0, e = 0;
  25. 	int zeroes = 0;
  26. 	int ans = 0;
  27.  
  28.  
  29. 	while(e<n){
  30. 		//* Calculate state
  31. 		if(a[e] == 0) zeroes++;
  32.  
  33.  
  34. 		if(zeroes <= k){
  35. 			//* Valid Wndow => Compute Result && expand 
  36. 			ans = max(ans, (e-s+1));
  37. 			e++;
  38. 		}
  39. 		else{
  40. 			//* Invalid window => Keep Shrink Window
  41. 			while(s<=e && zeroes>k){
  42. 				if(a[s] == 0) zeroes--;
  43. 				s++;
  44. 			}
  45.  
  46. 			//* Valid window => Compute Result && expand 
  47. 			ans = max(ans, (e-s+1));
  48. 			e++;
  49. 		}
  50. 	}
  51.  
  52. 	cout << ans << endl;
  53. }
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61. //* Template2 for Atmost k (i.e. <= k )
  62. //* 	(based on Cache Invalidation) 
  63.  
  64. void consistency2(int n, int k){
  65.  
  66. 	int zeroes = 0;
  67. 	int ans = 0;
  68. 	for(int s=0, e=0; e<n; e++){
  69.  
  70. 		//* Calculate state
  71. 		if(a[e] == 0) zeroes++;
  72.  
  73. 		//* Invalid window => Shrink 
  74. 		while(s<=e && zeroes>k){
  75. 			if(a[s] == 0 ) zeroes--;
  76. 			s++;
  77. 		}
  78.  
  79. 		//* Valid window guranteed => Compute Result
  80. 		ans = max(ans, (e-s+1));
  81. 	}
  82.  
  83. 	cout << ans << endl;
  84.  
  85. }
  86.  
  87.  
  88.  
  89.  
  90.  
  91. void solve() {
  92.  
  93. 	int n, k;
  94. 	cin >> n >> k;
  95. 	a.resize(n);
  96. 	for(int i=0; i<n; i++) cin >> a[i];
  97.  
  98. 	consistency1(n, k);
  99. 	consistency2(n, k);
  100.  
  101. }
  102.  
  103.  
  104.  
  105.  
  106.  
  107. int32_t main() {
  108.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  109.  
  110.     int t = 1;
  111.     cin >> t;
  112.     while (t--) {
  113.         solve();
  114.     }
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
2
11 2
1 1 1 0 0 0 1 1 1 1 0
4 0
0 0 0 0
stdout 
6
6
0
0
https://ideone.com/gepgih
language:
C++14 (gcc 8.3)
created:
2 days 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!