Join Us
how is this ensuring that whole group sits together?
Entering edit mode
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define vi vector<int>
#define rep(i, l, r) for(int i = l; i<r; i++)
unordered_map<int,int> pref;
int solve(int ind, int mask, vi &a, vi &b, int n, int m, vector<vi> &dp){
if (mask == (1<<m) - 1) return 0;
if (ind == a.size() + 1) return -1e9;
int maxi = 0;
if (dp[ind][mask] != -1) return dp[ind][mask];
maxi = max(maxi, solve(ind+1, mask, a, b, n, m, dp));
for(int i=0; i<m; i++){
if (mask & (1 << i)) continue;
if (ind+b[i] > n) return -1e9;
int cost = pref[b[i]+ind-1] - pref[ind-1];
int f = cost + solve(ind+b[i], mask|(1<<i), a, b, n, m, dp);
maxi = max(maxi, f);
}
return dp[ind][mask] = maxi;
}
int32_t main(){
int n,m;
cin>>n>>m;
vector<int> a(n);
rep(i,0,n) cin>>a[i];
vi b(m);
rep(i,0,m) cin>>b[i];
for(int i=0; i<n; i++){
pref[i] = pref[i-1] + a[i];
}
pref[-1] = 0;
vector<vector<int>> dp(n, vector<int>(1<<m, -1));
cout << solve(0, 0, a, b, n, m, dp) << endl;
return 0;
}
This is my answer for question 2 according to me.
I applied basic bitmask dp. To calculate the sum (basically the profit for the owner), i just used a prefix map
Entering edit mode
For Question no. 1:-
I think we can apply Bitmask DP because constraints on M is small (<=13)
So basically, Firstly we have to make a prefix sum array of the costs of seat.
Create DP[N][Mask] table where Dp[I][mask] will tell the maximum profit, which can be created by assigning seats index=i to n such that "mask" groups are already assigned seats.
Transitions:-
at each index, we have 2 options:-
i) Leave this seat i.e. Assign to no group
=> dp[I][mask]= 0+fun(i+1,mask)
ii) Assign to some group that has not been assigned yet. It can be checked from the mask by iterating over all groups (max iterations<=13)
=> dp[I][mask]= profit by assigning (can be calculated from prefix array in O(1) )+fun(i+1, mask|curr_group )
So, take the option which is more profitable
Ans will be stored as dp[0][0]
Time complexity:-
O(2^13 * N * 13), I think it should pass
Entering edit mode
Dungeons and Dragons
#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool binary_searchh(vector<ll> &dragons,ll n,ll m,ll mid)
{
ll sum=0;
for(int i=0;i<n;i++)
{
sum+=min(mid,dragons[i]);
}
return sum>=m;
}
void solve()
{
ll n,m;
cin>>n>>m;
vector<ll> dragons(n);
for(int i=0;i<n;i++)
cin>>dragons[i];
ll start=0,end=1e9+1;
while(start<end)
{
ll mid=(start+end)/2;
if(binary_searchh(dragons,n,m,mid))
{
end=mid;
}
else
{
start=mid+1;
}
}
ll sum=0;
for(int i=0;i<n;i++)
{
sum+=min(start-1,dragons[i]);
dragons[i]=max((ll)0,dragons[i]-(start-1));
}
while(sum<m)
{
for(int i=0;i<n;i++)
{
if(dragons[i]>0)
{
dragons[i]--;
sum++;
}
if(sum==m)
break;
}
}
for(int i=0;i<n;i++)
{
cout<<dragons[i]<<" ";
}
cout<<"\n";
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}
Entering edit mode
public static void main(String args[]) throws IOException {
int n=in.nextInt();
int m=in.nextInt();
int a[]=in.readintarray(n);
int b[]=in.readintarray(m);
Arrays.sort(a);
Arrays.sort(b);
long sum=0;
for(int i=n-1;i>=0;i--){
if(m==0)break;
sum+=a[i];
m--;
}
print(sum);
}will the first question be in this way can anyone share a test case?
Loading Similar Posts
#include<bits/stdc++.h>
#define endl "\n"
#define ff first
#define ss second
#define int long long
typedef long long ll;
typedef long double ld;
using namespace std;
#ifndef ONLINE_JUDGE
#include "include/debug.h"
#else
#define debugarr(a, n) 42
#define debug(...) 42
#endif
void code(int TC){
int n, m; cin >> n >> m;
vector<vector<pair<int, int>>> G(n + 5);
vector<int> a(n + 5);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int j = 0; j < m; j++){
int u, v; cin >> u >> v;
G[u].push_back({v, j});
G[v].push_back({u, j});
}
int all = accumulate(a.begin(), a.end(), 0ll);
vector<int> p(n + 1), sz(n + 5, 1), s(a.begin(), a.end());
iota(p.begin(), p.end(), 0);
function<int(int)> getpar = [&](int u){
if(u == p[u]) return u;
return p[u] = getpar(p[u]);
};
function<void(int, int)> merge = [&](int u, int v){
u = getpar(u), v = getpar(v);
if(u != v){
if(sz[u] < sz[v]) swap(u, v);
if(sz[u] == sz[v] && v < u) swap(u, v);
p[v] = u, sz[u] += sz[v], s[u] += s[v];
}
};
int id = 0;
vector<int> I(n + 5);
function<void(int, int)> dfs = [&](int u, int edge){
for(auto [v, e] : G[u]){
if(e == edge) continue;
if(I[v]){
I[u] = min(I[u], I[v]);
merge(u, v);
continue;
}
I[v] = ++id;
dfs(v, e);
I[u] = min(I[v], I[u]);
if(I[u] == I[v]) merge(u, v);
}
};
I[1] = ++id;
dfs(1, -1);
debug(p);
vector<vector<int>> T(n + 5);
vector<set<int>> ap(n + 5);
for(int i = 1; i <= n; i++){
for(auto [v, e] : G[i]){
if(getpar(i) != getpar(v)) T[getpar(i)].push_back(getpar(v)), ap[getpar(i)].insert(i);
}
}
vector<int> sum(n + 5);
int ansa = 0, ansb = 0;
for(int i = 1; i <= n; i++) p[i] = getpar(i);
function<void(int, int)> calc = [&](int u, int par){
int cur = s[u];
for(auto v : T[u]){
if(v == par) continue;
calc(v, u);
cur += sum[v];
}
sum[par] = all - cur;
for(auto art : ap[u]){
vector<int> V;
int now = 0;
for(auto [v, e] : G[art]){
if(p[v] != u) V.push_back(sum[p[v]]), now += sum[p[v]];
}
V.push_back(all - now - a[art]);
int k = V.size();
sort(V.begin(), V.end());
if(k == 1){
if(ansa == 0) ansb = max(ansb, V[0]);
}
else if(V[k - 2] > ansa) ansa = V[k - 2], ansb = V[k - 1];
else if(V[k - 2] == ansa && ansb < V[k - 2]) ansb = V[k - 2];
}
sum[par] = 0;
sum[u] = cur;
};
calc(p[1], 0);
cout << ansa << " " << ansb << endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);cerr.tie(0);
cout.precision(30);
int TT = 1; cin >> TT;
for (int TC = 1; TC <= TT; TC++)
code(TC);
return 0;
}