Submission #3418723
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i) #define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i) typedef long long ll; template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;} template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;} inline int read(){ int x; char c; int f=1; while((c=getchar())!='-' && (c>'9' || c<'0')); if(c=='-') f=-1,c=getchar(); x=c^'0'; while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'); return x*f; } inline ll readll(){ ll x; char c; int f=1; while((c=getchar())!='-' && (c>'9' || c<'0')); if(c=='-') f=-1,c=getchar(); x=c^'0'; while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0'); return x*f; } const int maxn=51,inf=0x3f3f3f3f; struct point{ int w,t;ll v; bool operator <(const point &rhs) const{ return v*rhs.w<rhs.v*w; } }a[maxn]; int fa[maxn]; ll f[maxn*maxn*maxn]; int main(){ int n=read(),X=read(),D=read(); a[1].v=read(),a[1].w=1,a[1].t=inf; REP(i,2,n) a[i].v=read(),fa[i]=read(),a[i].t=D,a[i].w=1; DREP(i,n,2) a[fa[i]].w+=a[i].w,a[fa[i]].v+=a[i].v; sort(a+1,a+n+1); int Max=min(n*n*n,X); REP(i,1,Max) f[i]=1e18; REP(i,1,n) REP(l,1,min(n,a[i].t)) DREP(j,Max,a[i].w) chkmin(f[j],f[j-a[i].w]+a[i].v); ll ans=0; REP(i,0,Max){ ll res=X-f[i],val=i; if(res<0) continue; REP(j,1,n){ ll cur=min((ll)a[j].t-n,res/a[j].v); if(cur<0) continue; res-=cur*a[j].v; val+=cur*a[j].w; } chkmax(ans,val); } printf("%lld\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Sweet Alchemy |
User | zhou888 |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 1612 Byte |
Status | AC |
Exec Time | 363 ms |
Memory | 1280 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 | 306 ms | 1280 KB |
b06 | AC | 8 ms | 1280 KB |
b07 | AC | 8 ms | 1280 KB |
b08 | AC | 16 ms | 1280 KB |
b09 | AC | 15 ms | 1280 KB |
b10 | AC | 355 ms | 1280 KB |
b11 | AC | 310 ms | 1280 KB |
b12 | AC | 358 ms | 1280 KB |
b13 | AC | 358 ms | 1280 KB |
b14 | AC | 1 ms | 256 KB |
b15 | AC | 1 ms | 256 KB |
b16 | AC | 250 ms | 1152 KB |
b17 | AC | 1 ms | 256 KB |
b18 | AC | 2 ms | 256 KB |
b19 | AC | 1 ms | 256 KB |
b20 | AC | 6 ms | 384 KB |
b21 | AC | 291 ms | 1152 KB |
b22 | AC | 49 ms | 512 KB |
b23 | AC | 1 ms | 256 KB |
b24 | AC | 307 ms | 1280 KB |
b25 | AC | 92 ms | 1280 KB |
b26 | AC | 307 ms | 1280 KB |
b27 | AC | 315 ms | 1280 KB |
b28 | AC | 181 ms | 1280 KB |
b29 | AC | 50 ms | 1280 KB |
b30 | AC | 307 ms | 1280 KB |
b31 | AC | 307 ms | 1280 KB |
b32 | AC | 310 ms | 1280 KB |
b33 | AC | 307 ms | 1280 KB |
b34 | AC | 322 ms | 1152 KB |
b35 | AC | 1 ms | 256 KB |
b36 | AC | 1 ms | 256 KB |
b37 | AC | 1 ms | 256 KB |
b38 | AC | 2 ms | 256 KB |
b39 | AC | 6 ms | 256 KB |
b40 | AC | 259 ms | 1152 KB |
b41 | AC | 1 ms | 256 KB |
b42 | AC | 48 ms | 512 KB |
b43 | AC | 1 ms | 256 KB |
b44 | AC | 316 ms | 1280 KB |
b45 | AC | 318 ms | 1280 KB |
b46 | AC | 335 ms | 1280 KB |
b47 | AC | 332 ms | 1280 KB |
b48 | AC | 331 ms | 1280 KB |
b49 | AC | 316 ms | 1280 KB |
b50 | AC | 355 ms | 1280 KB |
b51 | AC | 355 ms | 1280 KB |
b52 | AC | 315 ms | 1280 KB |
b53 | AC | 315 ms | 1280 KB |
b54 | AC | 12 ms | 384 KB |
b55 | AC | 59 ms | 640 KB |
b56 | AC | 284 ms | 1152 KB |
b57 | AC | 320 ms | 1280 KB |
b58 | AC | 363 ms | 1280 KB |
b59 | AC | 321 ms | 1280 KB |
b60 | AC | 326 ms | 1280 KB |
b61 | AC | 328 ms | 1280 KB |
b62 | AC | 317 ms | 1280 KB |
b63 | AC | 316 ms | 1280 KB |