Competitive-Programming/another_string.cpp at master · Code-Cube-NITP/Competitive-Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
#definefastioios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#defineendl'\n'
#defineintlonglongint
usingnamespacestd;
#definepii pair <int, int>
#definemii map<int, int>
#definepb push_back
#definedeb(x) cout << #x << "" << x << endl
#definedeb2(x, y) cout << #x << "" << x << "" << #y << "" << y << endl
#defineLoop(s, e, itr) for (int itr = s; itr < e; itr++)
#defineloop(n) for(int i = 0; i < n; i++)
#definevin vector<int>
#definew(t) int tc; cin >> tc; for(int t = 1; t <= tc; t++)
#definevec vector
#definemk_arr(n, t, s) t* n = new t[s]; loop(s) cin >> n[i];
#definemi_arr(n, s) int* n = newint[s]; loop(s) cin >> n[i];
#definearr_out(n, s) Loop(0, s, lout) cout << n[lout] << "";
#definepi(x) printf("%lld ", x);
#definemod1000000007


int32_tmain(){
int n;
 string str;
 cin >> n;
 cin >> str;
 vin ones;
int len = str.length();
for(int i = 0; i < len; i++) if(str[i] == '1') ones.pb(i);
 string s1 = str;
 str += '1';
 str = '1'+str;
 map<int, pii> cnt;
for(auto i : ones){
int c = 1;
int ii = i+1;
while(str[ii-1] == '0') c++, ii--;
 cnt[i].first = c;
 c = 1;
 ii = i+1;
while(str[ii+1] == '0') c++, ii++;
 cnt[i].second = c;
 }
if(n > ones.size()) cout << 0 << endl;
elseif(n == 0){
// int i = 0;
int ans = 0;
 len = s1.length();
int temp = 0;
loop(len){
if(s1[i] == '0') temp++;
else{
 ans += (temp*(temp+1))/2;
 temp = 0;
 }
 }
 ans += (temp*(temp+1))/2;
 cout << ans;
 }
else{
int ans = 0;
int s = ones.size() - n + 1;
// deb(s);
loop(s){
// deb(cnt[ones[i]].first);
// deb(cnt[ones[i+n-1]].second);
 ans += cnt[ones[i]].first*cnt[ones[i+n-1]].second;
 }
 cout << ans << endl;
 }
}