Giving TLE on MAXHAMDistance

general
1

include <bits/stdc++.h>
include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;//cpp_int for big fact

define ull unsigned long long
define ll long long
int dr[8]={2,2,-2,-2,1,-1,1,-1};
int dc[8]={1,-1,1,-1,2,2,-2,-2};
int kingrow[8] = {1,1,0,-1,-1,-1,0,1};
int kingcol[8] = {0,1,1,1,0,-1,-1,-1};
int xa[4] = {0,0,1,-1};
int ya[4] = {1,-1,0,0};

bool isPrime(ll n)
{
if (n <= 1)
return false;
if (n <= 3)
return true;

if (n % 2 == 0 || n % 3 == 0)
    return false;

for (ll i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0)
        return false;

return true;

}

void input(int a,int n)
{
for(int i=0;i<n;i++)
cin>>a[i];
}

bool isPalindrome(string s)
{
string temp=s;
reverse(temp.begin(),temp.end());
return (s==temp);
}

bool isVowel(char c)
{
if(c==‘a’ || c==‘e’ || c==‘i’||c==‘o’||c==‘u’||c==‘A’||c==‘E’||c==‘I’||c==‘O’||c==‘U’)return true;
else return false;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
vectorv[m];
for(int i = 0;i<m;i++)
{
string s;
cin>>s;
v[i].push_back(s);
}
ll ans = 0;
for(int i=0;i<n;i++)
{
ll countone = 0,countzero = 0;
ll countmark = 0;
for(int j = 0;j<m;j++)
{
string s = v[j][0];
if(s[i]==‘0’)countzero++;
else if(s[i]==‘1’) countone++;
else countmark++;
}
if(countone==countzero)
{
if(countmark%2==0)
{
countzero+=(countmark)/2;
countone += (countmark)/2;
ans += (countzerocountone);
}
else
{
countzero+=(countmark)/2;
countone += ((countmark)/2)+1;
ans += (countzerocountone);
}
}
else
{
if(countone > countzero)
{
ll dif = countone - countzero;
ll minval = min(dif,countmark);
countzero+=minval;
countzero+=(countmark-minval)/2;
countone+=(countmark-minval)/2;
if((countmark-minval)%2==1)countone++;
ans += (countzerocountone);
}
else
{
ll dif = countzero - countone;
ll minval = min(dif,countmark);
countone+=minval;
countzero+=(countmark-minval)/2;
countone+=(countmark-minval)/2;
if((countmark-minval)%2==1)countone++;
ans += (countzerocountone);
}
}

    }
    cout<<ans<<"\n";
}
return 0;

}