Submission #3383486
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define int long long #define INF 1e9+10 int n,X,D,ans,cnt,dp[125003]; int w[53],val[53],pos[53]; int tot,V[53*53],W[53*53]; inline int read(){ int x=0,k=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*k; } struct edge{ int cnp,to[53],last[53],head[53]; edge(){cnp=1;} void add(int u,int v){ to[cnp]=v,last[cnp]=head[u],head[u]=cnp++; } }E1; void dfs(int u){ val[u]=1; for(int i=E1.head[u];i;i=E1.last[i]){ int v=E1.to[i]; dfs(v); w[u]+=w[v],val[u]+=val[v]; } cnt+=val[u]*n; pos[u]=u; } inline bool cmp(int x,int y){ return val[x]*w[y]>val[y]*w[x]; } inline void Get_min(int &x,int y){ x=x<y?x:y; } signed main(){ n=read(),X=read(),D=read(); w[1]=read(); for(int i=2;i<=n;i++){ w[i]=read(); int x=read(); E1.add(x,i); } dfs(1); sort(pos+1,pos+n+1,cmp); int tmp=min(n,D); for(int i=1;i<=cnt;i++){ dp[i]=INF; } for(int i=1;i<=n;i++){ int len=1,lim=tmp; while(lim>=len){ V[++tot]=len*val[pos[i]]; W[tot]=len*w[pos[i]]; lim-=len,len<<=1; } if(lim){ V[++tot]=lim*val[pos[i]],W[tot]=lim*w[pos[i]]; } } for(int i=1;i<=tot;i++){ for(int j=cnt;~j;j--){ if(j>=V[i]){ Get_min(dp[j],dp[j-V[i]]+W[i]); } } } int ans=0; for(int i=0;i<=cnt;i++){ if(dp[i]>X){ continue; } int ret=i,left=X-dp[i]; for(int j=1;j<=n;j++){ int tem=pos[j],used=min(max(D-n,0LL),left/w[tem]); if(tem==1) used=left/w[tem]; left-=w[tem]*used; ret+=val[tem]*used; } ans=max(ans,ret); } printf("%lld\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Sweet Alchemy |
User | mengdai |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 1948 Byte |
Status | AC |
Exec Time | 78 ms |
Memory | 768 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 900 / 900 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03 |
All | a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46, b47, b48, b49, b50, b51, b52, b53, b54, b55, b56, b57, b58, b59, b60, b61, b62, b63 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
a01 | AC | 1 ms | 256 KB |
a02 | AC | 1 ms | 256 KB |
a03 | AC | 1 ms | 256 KB |
b04 | AC | 1 ms | 256 KB |
b05 | AC | 26 ms | 768 KB |
b06 | AC | 1 ms | 768 KB |
b07 | AC | 1 ms | 256 KB |
b08 | AC | 7 ms | 768 KB |
b09 | AC | 2 ms | 256 KB |
b10 | AC | 75 ms | 768 KB |
b11 | AC | 7 ms | 256 KB |
b12 | AC | 78 ms | 768 KB |
b13 | AC | 77 ms | 768 KB |
b14 | AC | 1 ms | 256 KB |
b15 | AC | 1 ms | 256 KB |
b16 | AC | 16 ms | 512 KB |
b17 | AC | 1 ms | 256 KB |
b18 | AC | 1 ms | 256 KB |
b19 | AC | 1 ms | 256 KB |
b20 | AC | 2 ms | 256 KB |
b21 | AC | 22 ms | 384 KB |
b22 | AC | 6 ms | 256 KB |
b23 | AC | 1 ms | 256 KB |
b24 | AC | 7 ms | 384 KB |
b25 | AC | 4 ms | 384 KB |
b26 | AC | 18 ms | 640 KB |
b27 | AC | 14 ms | 384 KB |
b28 | AC | 5 ms | 384 KB |
b29 | AC | 6 ms | 384 KB |
b30 | AC | 8 ms | 384 KB |
b31 | AC | 26 ms | 768 KB |
b32 | AC | 29 ms | 768 KB |
b33 | AC | 7 ms | 384 KB |
b34 | AC | 69 ms | 768 KB |
b35 | AC | 1 ms | 256 KB |
b36 | AC | 1 ms | 256 KB |
b37 | AC | 1 ms | 256 KB |
b38 | AC | 1 ms | 256 KB |
b39 | AC | 2 ms | 256 KB |
b40 | AC | 14 ms | 384 KB |
b41 | AC | 1 ms | 256 KB |
b42 | AC | 5 ms | 256 KB |
b43 | AC | 1 ms | 256 KB |
b44 | AC | 16 ms | 384 KB |
b45 | AC | 16 ms | 384 KB |
b46 | AC | 44 ms | 512 KB |
b47 | AC | 39 ms | 512 KB |
b48 | AC | 39 ms | 512 KB |
b49 | AC | 16 ms | 384 KB |
b50 | AC | 75 ms | 768 KB |
b51 | AC | 75 ms | 768 KB |
b52 | AC | 14 ms | 384 KB |
b53 | AC | 15 ms | 384 KB |
b54 | AC | 5 ms | 256 KB |
b55 | AC | 11 ms | 384 KB |
b56 | AC | 12 ms | 384 KB |
b57 | AC | 22 ms | 384 KB |
b58 | AC | 75 ms | 768 KB |
b59 | AC | 23 ms | 384 KB |
b60 | AC | 30 ms | 512 KB |
b61 | AC | 33 ms | 512 KB |
b62 | AC | 17 ms | 384 KB |
b63 | AC | 29 ms | 640 KB |