Advertisement
Underdogs

cf round

Dec 6th, 2016
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair<int,int> ii;
  6. #define pii 3.141592654
  7. #define INF 1000000007
  8. #define N 1005
  9. #define M 10
  10. #define F first
  11. #define S second
  12. #define pb push_back
  13. #define mp make_pair
  14. #define si(x) scanf("%d",&x)
  15. #define sif(x) scanf("%lf",&x)
  16. #define sil(x) scanf("%I64d",&x)
  17. #define pi(x) printf("%d\n",x)
  18. #define pis(x) printf("%d ",x)
  19. #define cpi(x) printf("Case %d: ",x)
  20. #define pil(x) printf("%I64d\n",x)
  21. #define rep(i,n,m) for(int i = n; i< m; i++)
  22. #define reps(i,n,m) for(int i = n; i >= m; i--)
  23. #define lft(x) x*2
  24. #define rgt(x) x*2+1
  25.  
  26. int n,m,x,y,cmp,mark[N];
  27. vector<int>ad[N];
  28. int weight[N],w,allw[N],allb[N],nxt[N];
  29. pair<int,int>pa[N];
  30. ll beauty[N],dp[N][N];
  31.  
  32. void go(int u)
  33. {
  34.     mark[u] = cmp;
  35.     allw[cmp] += weight[u];
  36.     allb[cmp] += beauty[u];
  37.  
  38.  
  39.     rep(i,0,ad[u].size()){
  40.         int v = ad[u][i];
  41.         if(!mark[v]){
  42.             go(v);
  43.         }
  44.     }
  45. }
  46.  
  47. ll go1(int pos,int tot)
  48. {
  49.     if(tot > w) return -1e12;
  50.     if(pos > n) return 0;
  51.  
  52.     ll &ret = dp[pos][tot];
  53.     if(ret != -1) return ret;
  54.  
  55.     ret = 0;
  56.  
  57.     int p = nxt[pos];
  58.     ll a = 0;
  59.     rep(i,pos,p){
  60.         a = max(a,beauty[pa[i].S] + go1(nxt[i],tot+weight[pa[i].S]));
  61.     }
  62.     ll b = go1(nxt[pos],tot);
  63.     ll c = allb[pa[pos].F] + go1(nxt[pos],tot+allw[pa[pos].F]);
  64.  
  65.     return max(a,max(b,c));
  66. }
  67.  
  68. int main()
  69. {
  70.     memset(dp,-1,sizeof(dp));
  71.     si(n);si(m);si(w);
  72.     rep(i,1,n+1) si(weight[i]);
  73.     rep(i,1,n+1) sil(beauty[i]);
  74.  
  75.     rep(i,0,m){
  76.         si(x);si(y);
  77.         ad[x].pb(y);
  78.         ad[y].pb(x);
  79.     }
  80.     cmp = 0;
  81.     rep(i,1,n+1){
  82.         if(!mark[i]){
  83.             cmp++;
  84.             go(i);
  85.         }
  86.     }
  87.  
  88.  
  89.     rep(i,1,n+1){
  90.         pa[i].F = mark[i];
  91.         pa[i].S = i;
  92.     }
  93.  
  94.     sort(pa+1,pa+n+1);
  95.     int u = n + 1,y = pa[n].F;
  96.     reps(i,n,1){
  97.         if(y == pa[i].F){
  98.             nxt[i] = u;
  99.         }
  100.         else{
  101.             u = i + 1;
  102.             y = pa[i].F;
  103.             nxt[i] = u;
  104.         }
  105.     }
  106.  
  107.     ll ans = go1(1,0);
  108.  
  109.     pil(ans);
  110.  
  111.  
  112.     return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement