Join Us
Kindly do let me know if this approch is correct
Entering edit mode
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int factor(vector<vector<int>>&a,int n,int m)
{
int count=0;
for(int i=0;i<n;i++)
{
int flag=0;
for(int j=0;j<m;j++)
{
if(a[i][j]==0)
{
flag=1;
break;
}
}
if(flag==0)
count++;
}
return count;
}
int maxfactor(vector<vector<int>>&a,int n,int m,int k,int col)
{
if(k==0)
{
return factor(a,n,m);
}
if(col>=m)
return 0;
int temp=maxfactor(a,n,m,k,col+1);
for(int i=0;i<n;i++)
{
a[i][col]=!a[i][col];
}
int temp2=maxfactor(a,n,m,k-1,col);
for(int i=0;i<n;i++)
{
a[i][col]=!a[i][col];
}
return max(temp,temp2);
}
int main()
{
int n,m,k;
cin>>n>>m;
vector<vector<int>>a(n,vector<int>(m));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
cin>>k;
cout<<maxfactor(a,n,m,k,0);
return 0;
}
Entering edit mode
ll dp[21][21] ;
ll cal(ll j , ll n ,ll m , vector<vll>&arr, ll mask )
{
if(j==m)
{
ll ans =0 ;
fl(i ,0 ,n )
{
ll f= 0;
fl(j , 0, m )
{
if(mask&(1<<j))
{
if(arr[i][j]>0)
{
f=1 ;
break ;
}
}
else
{
if(arr[i][j]<0)
{
f=1 ;
break ;
}
}
}
if(!f)
ans++ ;
}
return ans ;
}
if(dp[j][mask]!=-1)
return dp[j][mask];
ll t=0 ,nt =0 ;
t = cal(j+1, n ,m , arr , mask|(1<<(j))) ;
nt= cal(j+1, n , m, arr ,mask ) ;
return dp[j][mask] = max(t, nt ) ;
}
void solve()
{
ll n ,m , k ;cin >> n>> m>> k ;
vector<vll>arr(n , vll(m)) ;
fl(i ,0 ,n )
{
fl(j ,0 , m)
cin >> arr[i][j] ;
}
memset(dp , -1 ,sizeof(dp)) ;
cout << cal(0 , n , m ,arr , 0 ) ;
}
Loading Similar Posts
it is brute force ,will it pass all testcases ?
I Think we can not use STL ..