A contest full of frustration
1#include <bits/stdc++.h>
2
3using namespace std;
4
5typedef long long ll;
6typedef pair<int, int> ii;
7
8int main()
9{
10 int n, k, x;
11 scanf("%d %d %d", &n, &k, &x);
12
13 int tot = 0;
14 for(int i = 0; i < n; i++) {
15 int num;
16 scanf("%d", &num);
17
18 if(i < n - k)
19 tot += num;
20 else
21 tot += x;
22 }
23 printf("%d\n", tot);
24
25 return 0;
26}A pretty good one!
Binary search won’t work, don’t be tricked.
We can keep a $sum$, initialized with $0$. If we encounter a $0$, we subtract the $sum$ by 1, otherwise, we add $1$ to $sum$.
It is easy to see that whenever you have the same $sum$, this implies that the number of $+1$ and $-1$ is the same between the interval! Using this property we can get the maximum balanced substring.
Keep in mind of a tricky case, $01101010$ :)
1#include <bits/stdc++.h>
2
3using namespace std;
4
5typedef long long ll;
6typedef pair<int, int> ii;
7
8int main()
9{
10 int len;
11 char inp[100010];
12 scanf("%d", &len);
13 scanf("%s", inp + 1); // case 01101010
14
15 int sum = 0;
16 map<int, int> loc;
17 int ans = 0;
18 loc[0] = 0;
19 for(int i = 1; i <= len; i++) {
20 if(inp[i] == '1')
21 sum++;
22 else
23 sum--;
24
25 auto it = loc.find(sum);
26 if(it != loc.end()) {
27 ans = max(ans, i - it->second);
28 } else {
29 loc[sum] = i;
30 }
31 }
32 printf("%d\n", ans);
33
34 return 0;
35}