➤ Problem Link : 225C. Barcode
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int n,m,x,y;
cin>>n>>m>>x>>y;
char arr[n+1][m+1];
int whites[m+1]={0};
ll cum[m+1];
pair<ll,ll> minPixels[m+1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>arr[i][j];
if(arr[i][j]=='.')
whites[j]++;
}
}
cum[0]=0;
cum[1]=whites[1];
for(int i=2;i<=m;i++)
cum[i]=whites[i]+cum[i-1];
minPixels[0].first=minPixels[0].second=0;
for(int i=1;i<=m;i++)
{
minPixels[i].first=minPixels[i].second=INT_MAX;
for(int j= i-x+1;j>=i-y+1 && j>=1 ;j--)
{
minPixels[i].second=min(minPixels[i].second,cum[i]-cum[j-1]+minPixels[j-1].first);
minPixels[i].first=min(minPixels[i].first,(i-j+1)*n - cum[i]+cum[j-1] + minPixels[j-1].second);
}
// cout<<i<<" "<<minPixels[i].first<<" "<<minPixels[i].second<<"\n";
}
cout<<min(minPixels[m].first,minPixels[m].second);
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
➤ Problem Link : 225C. Barcode
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int n,m,x,y;
cin>>n>>m>>x>>y;
char arr[n+1][m+1];
int whites[m+1]={0};
ll cum[m+1];
pair<ll,ll> minPixels[m+1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>arr[i][j];
if(arr[i][j]=='.')
whites[j]++;
}
}
cum[0]=0;
cum[1]=whites[1];
for(int i=2;i<=m;i++)
cum[i]=whites[i]+cum[i-1];
minPixels[0].first=minPixels[0].second=0;
for(int i=1;i<=m;i++)
{
minPixels[i].first=minPixels[i].second=INT_MAX;
for(int j= i-x+1;j>=i-y+1 && j>=1 ;j--)
{
minPixels[i].second=min(minPixels[i].second,cum[i]-cum[j-1]+minPixels[j-1].first);
minPixels[i].first=min(minPixels[i].first,(i-j+1)*n - cum[i]+cum[j-1] + minPixels[j-1].second);
}
// cout<<i<<" "<<minPixels[i].first<<" "<<minPixels[i].second<<"\n";
}
cout<<min(minPixels[m].first,minPixels[m].second);
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.