Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> ii;
- #define pii 3.141592654
- #define INF 1000000007
- #define N 1005
- #define M 10
- #define F first
- #define S second
- #define pb push_back
- #define mp make_pair
- #define si(x) scanf("%d",&x)
- #define sif(x) scanf("%lf",&x)
- #define sil(x) scanf("%I64d",&x)
- #define pi(x) printf("%d\n",x)
- #define pis(x) printf("%d ",x)
- #define cpi(x) printf("Case %d: ",x)
- #define pil(x) printf("%I64d\n",x)
- #define rep(i,n,m) for(int i = n; i< m; i++)
- #define reps(i,n,m) for(int i = n; i >= m; i--)
- #define lft(x) x*2
- #define rgt(x) x*2+1
- int n,m,x,y,cmp,mark[N];
- vector<int>ad[N];
- int weight[N],w,allw[N],allb[N],nxt[N];
- pair<int,int>pa[N];
- ll beauty[N],dp[N][N];
- void go(int u)
- {
- mark[u] = cmp;
- allw[cmp] += weight[u];
- allb[cmp] += beauty[u];
- rep(i,0,ad[u].size()){
- int v = ad[u][i];
- if(!mark[v]){
- go(v);
- }
- }
- }
- ll go1(int pos,int tot)
- {
- if(tot > w) return -1e12;
- if(pos > n) return 0;
- ll &ret = dp[pos][tot];
- if(ret != -1) return ret;
- ret = 0;
- int p = nxt[pos];
- ll a = 0;
- rep(i,pos,p){
- a = max(a,beauty[pa[i].S] + go1(nxt[i],tot+weight[pa[i].S]));
- }
- ll b = go1(nxt[pos],tot);
- ll c = allb[pa[pos].F] + go1(nxt[pos],tot+allw[pa[pos].F]);
- return max(a,max(b,c));
- }
- int main()
- {
- memset(dp,-1,sizeof(dp));
- si(n);si(m);si(w);
- rep(i,1,n+1) si(weight[i]);
- rep(i,1,n+1) sil(beauty[i]);
- rep(i,0,m){
- si(x);si(y);
- ad[x].pb(y);
- ad[y].pb(x);
- }
- cmp = 0;
- rep(i,1,n+1){
- if(!mark[i]){
- cmp++;
- go(i);
- }
- }
- rep(i,1,n+1){
- pa[i].F = mark[i];
- pa[i].S = i;
- }
- sort(pa+1,pa+n+1);
- int u = n + 1,y = pa[n].F;
- reps(i,n,1){
- if(y == pa[i].F){
- nxt[i] = u;
- }
- else{
- u = i + 1;
- y = pa[i].F;
- nxt[i] = u;
- }
- }
- ll ans = go1(1,0);
- pil(ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement