I am trying to solve round #383 problem D (div 2):
Problem statement:here
I can complete every step up till the usage of DP. In my code, I used 2-D DP like what was mentioned in the editorial. Somehow, my code is failing the following test case:
10 5 100
6 18 35 6 87 58 4 53 37 71
465782 57034 547741 748298 315223 370368 679320 349012 9740 622511
1 2
10 9
6 7
3 6
7 1
Expected Output: 2050129
My Program Output: 1836591
My attempt:
#include <iostream>
#include <vector>
#include <unordered_map>
//#define debug
using namespace std;
#define ll long long
#define v64 vector<ll>
#define um unordered_map<ll,ll>
#define mp make_pair
ll n,m,w,a,b;
typedef struct woman {
ll w, b;
} woman;
woman ww[1005];
ll par[1005], rk[1005],dp[1005][1005];
um cw, cb;
int val[1005];
ll find(ll x) {
ll p = x;
if(par[x]!=x) p = find(par[x]);
return par[x] = p;
}
inline void un(ll x,ll y) {
ll px = find(x), py = find(y);
if(px != py) {
if(rk[px] > rk[py]) {
par[py] = px;
rk[px] += rk[py];
} else {
par[px] = py;
rk[py] += rk[px];
}
}
}
ll solve(ll cur, ll t) {
if(dp[cur][t]!=-1) return dp[cur][t];
if(cur <= n && t>0) {
if(ww[cur].w<=t) {
if(val[find(cur)]) {
val[find(cur)] = 0;
ll a1 = 0;
if(cw[find(cur)]<=t) a1 = cb[find(cur)]+solve(cur+1,t-cw[find(cur)]);
ll a2 = ww[cur].b+solve(cur+1,t-ww[cur].w);
val[find(cur)] = 1;
ll a3 = solve(cur+1,t);
return dp[cur][t] = max(a1,max(a2,a3));
} else {
return dp[cur][t] = solve(cur+1,t);
}
} else {
return dp[cur][t] = solve(cur+1,t);
}
}
return dp[cur][t]=0;
}
int main(void) {
#ifdef debug
freopen("in","r",stdin);
#else
ios_base::sync_with_stdio(false);
cin.tie(0);
#endif
cin >> n >> m >> w;
fill_n(rk,n+1,1);
fill_n(val,n+1,1);
for(int i = 1; i <= n; ++i) fill_n(dp[i],w+1,-1);
for(int i = 1; i <= n; ++i) {
cin >> ww[i].w;
par[i] = i;
}
for(int i = 1; i <= n; ++i) {
cin >> ww[i].b;
}
for(int i = 1; i <= m; ++i) {
cin >> a >> b;
un(a,b);
}
for(int i = 1 ; i <= n; ++i) {
cw[find(i)] += ww[i].w;
cb[find(i)] += ww[i].b;
}
cout << solve(1,w) << endl;
return 0;
}
If I remove the DP (from the solve function), my program will pass the test case. Hence, it is clear that my DP is wrong. However, I do not know how to write the DP properly. Could someone please advise me on why my code is wrong?