main.cpp (1514B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 using namespace std; 11 12 // k defines how many characters can be swapped at the start 13 // 14 15 int main() { 16 17 int testCases, n, k; 18 string s = ""; 19 cin >> testCases; 20 21 for(int z = 0; z < testCases; ++z) { 22 cin >> n; 23 cin >> k; 24 cin >> s; 25 26 int zeroCount = 0; 27 int oneCount = 0; 28 for(int i = 0; i < n; ++i) { 29 if(s[i] == '0') { 30 zeroCount += 1; 31 } else { 32 oneCount += 1; 33 } 34 } 35 36 int flipped = 0; 37 38 if(zeroCount > oneCount) { 39 for(int i = 0; i < n && flipped < k; ++i) { 40 if(s[i] == '1') { 41 s[i] = '0'; 42 flipped += 1; 43 zeroCount += 1; 44 oneCount -= 1; 45 } 46 } 47 } else { 48 for(int i = 0; i < n && flipped < k; ++i) { 49 if(s[i] == '0') { 50 s[i] = '1'; 51 flipped += 1; 52 zeroCount -= 1; 53 oneCount += 1; 54 } 55 } 56 } 57 58 long long res = 1; 59 60 for(int i = 1; i <= zeroCount; ++i) { 61 res += (zeroCount + 1) - i; 62 } 63 for(int i = 1; i <= oneCount; ++i) { 64 res += (oneCount + 1) - i; 65 } 66 cout << res << '\n'; 67 68 } 69 }