➤ Problem Link : 741B. Arpa's weak amphitheater and Mehrdad's valuable Hoses
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int parent[1001];
int find(int v)
{
if(parent[v]==v)
return v;
return parent[v]=find(parent[v]);
}
int main()
{
int n,m,w,x,y,a,b;
cin>>n>>m>>w;
pair<int,ll> hose[n+1];
// vector<int> adj[n+1];
// bool visited[n+1];
// memset(visited,0,sizeof(visited));
for(int i=1;i<=n;i++)
cin>>hose[i].first;
for(int i=1;i<=n;i++)
cin>>hose[i].second;
for(int i=1;i<=n;i++)
parent[i]=i;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
a=find(x);
b=find(y);
if(a!=b)
parent[b]=a;
}
int k=0;
unordered_map<int,int> mp;
for(int i=1;i<=n;i++)
{
parent[i]=find(i);
if(parent[i]==i)
mp[i]=++k;
}
vector<int> comp[k+1];
for(int i=1;i<=n;i++)
comp[mp[parent[i]]].push_back(i);
/* for(int i=1;i<=k;i++)
{
cout<<i<<" ";
for(int j : comp[i])
cout<<j<<" ";
cout<<endl;
}*/
ll dp[k+1][w+1];
memset(dp,0,sizeof(dp));
vector<int> v;
ll sumW,sumB;
ll ans=0;
for(int p=1;p<=k;p++)
{
v = comp[p];
sumW=0,sumB=0;
for(int i=0;i<v.size();i++)
{
for(int j=1;j<=w;j++)
{
if(p==1 && hose[v[i]].first<=j)
{
dp[1][j]=max(dp[1][j],hose[v[i]].second);
}
else if(p!=1)
{
dp[p][j]=max(dp[p][j],dp[p-1][j]);
if (hose[v[i]].first<=j)
dp[p][j]=max(dp[p][j],hose[v[i]].second+dp[p-1][j-hose[v[i]].first]);
}
ans=max(ans,dp[p][j]);
}
sumW+=hose[v[i]].first;
sumB+=hose[v[i]].second;
}
for(int j=1;j<=w;j++)
{
if(p==1 && sumW<=j)
{
dp[1][j]=max(dp[1][j],sumB);
}
else if(p!=1)
{
dp[p][j]=max(dp[p][j],dp[p-1][j]);
if (sumW<=j)
dp[p][j]=max(dp[p][j],sumB+dp[p-1][j-sumW]);
}
ans=max(ans,dp[p][j]);
}
/* for(int j=0;j<=w;j++)
cout<<dp[p][j]<<" ";
cout<<endl; */
}
cout<<ans;
}
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 : 741B. Arpa's weak amphitheater and Mehrdad's valuable Hoses
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int parent[1001];
int find(int v)
{
if(parent[v]==v)
return v;
return parent[v]=find(parent[v]);
}
int main()
{
int n,m,w,x,y,a,b;
cin>>n>>m>>w;
pair<int,ll> hose[n+1];
// vector<int> adj[n+1];
// bool visited[n+1];
// memset(visited,0,sizeof(visited));
for(int i=1;i<=n;i++)
cin>>hose[i].first;
for(int i=1;i<=n;i++)
cin>>hose[i].second;
for(int i=1;i<=n;i++)
parent[i]=i;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
a=find(x);
b=find(y);
if(a!=b)
parent[b]=a;
}
int k=0;
unordered_map<int,int> mp;
for(int i=1;i<=n;i++)
{
parent[i]=find(i);
if(parent[i]==i)
mp[i]=++k;
}
vector<int> comp[k+1];
for(int i=1;i<=n;i++)
comp[mp[parent[i]]].push_back(i);
/* for(int i=1;i<=k;i++)
{
cout<<i<<" ";
for(int j : comp[i])
cout<<j<<" ";
cout<<endl;
}*/
ll dp[k+1][w+1];
memset(dp,0,sizeof(dp));
vector<int> v;
ll sumW,sumB;
ll ans=0;
for(int p=1;p<=k;p++)
{
v = comp[p];
sumW=0,sumB=0;
for(int i=0;i<v.size();i++)
{
for(int j=1;j<=w;j++)
{
if(p==1 && hose[v[i]].first<=j)
{
dp[1][j]=max(dp[1][j],hose[v[i]].second);
}
else if(p!=1)
{
dp[p][j]=max(dp[p][j],dp[p-1][j]);
if (hose[v[i]].first<=j)
dp[p][j]=max(dp[p][j],hose[v[i]].second+dp[p-1][j-hose[v[i]].first]);
}
ans=max(ans,dp[p][j]);
}
sumW+=hose[v[i]].first;
sumB+=hose[v[i]].second;
}
for(int j=1;j<=w;j++)
{
if(p==1 && sumW<=j)
{
dp[1][j]=max(dp[1][j],sumB);
}
else if(p!=1)
{
dp[p][j]=max(dp[p][j],dp[p-1][j]);
if (sumW<=j)
dp[p][j]=max(dp[p][j],sumB+dp[p-1][j-sumW]);
}
ans=max(ans,dp[p][j]);
}
/* for(int j=0;j<=w;j++)
cout<<dp[p][j]<<" ";
cout<<endl; */
}
cout<<ans;
}
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.