Submission #3373824
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);
using namespace std;
namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;
void rec(int c, const vector<vi> &e, vi &v, vector<ll> &w){
v[c] = 1;
for(int i: e[c]){
rec(i, e, v, w);
v[c] += v[i];
w[c] += w[i];
}
}
int main(){
cin.tie(0); cin.sync_with_stdio(0);
int n, x, d; cin >> n >> x >> d;
vector<vi> e(n);
vi v(n), rem(n);
vector<ll> w(n);
rep(i, n){
cin >> w[i];
if(i){
int p; cin >> p; p--;
e[p].pb(i);
}
}
rec(0, e, v, w);
//dbg(v); dbg(w);
const int N = 65000;
vector<ll> dp(N, (ll)1e18);
dp[0] = 0;
rep(i, n) for(int j = N - 1; j >= 0; j--) if(dp[j] < 1e18){
int cnt = i == 0 ? inf : d, use = min(cnt, 50);
rem[i] = cnt - use;
for(int k = 1; k <= use; k++){
int nj = j + k * v[i];
if(nj >= N || dp[j] + k * w[i] > x) break;
dp[nj] = min(dp[nj], dp[j] + k * w[i]);
}
}
vector<tuple<int, ll, int>> u;
rep(i, n) u.emplace_back(v[i], w[i], rem[i]);
sort(all(u), [](tuple<int, ll, int> a, tuple<int, ll, int> b)
{ return get<1>(a) * get<0>(b) < get<1>(b) * get<0>(a); }
);
ll ans = 0;
rep(i, N) if(dp[i] <= x){
ll cnt = i;
ll cost = dp[i];
for(auto j : u) if(cost < x){
ll k = min((ll)get<2>(j), (x - cost) / get<1>(j));
cnt += k * get<0>(j);
cost += k * get<1>(j);
}
ans = max(ans, cnt);
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Sweet Alchemy |
User |
nadeko |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
2791 Byte |
Status |
AC |
Exec Time |
270 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 |
2 ms |
768 KB |
a02 |
AC |
2 ms |
768 KB |
a03 |
AC |
2 ms |
768 KB |
b04 |
AC |
2 ms |
768 KB |
b05 |
AC |
5 ms |
768 KB |
b06 |
AC |
5 ms |
768 KB |
b07 |
AC |
5 ms |
768 KB |
b08 |
AC |
8 ms |
768 KB |
b09 |
AC |
7 ms |
768 KB |
b10 |
AC |
252 ms |
768 KB |
b11 |
AC |
26 ms |
768 KB |
b12 |
AC |
267 ms |
768 KB |
b13 |
AC |
267 ms |
768 KB |
b14 |
AC |
2 ms |
768 KB |
b15 |
AC |
2 ms |
768 KB |
b16 |
AC |
5 ms |
768 KB |
b17 |
AC |
2 ms |
768 KB |
b18 |
AC |
2 ms |
768 KB |
b19 |
AC |
2 ms |
768 KB |
b20 |
AC |
9 ms |
768 KB |
b21 |
AC |
89 ms |
768 KB |
b22 |
AC |
28 ms |
768 KB |
b23 |
AC |
2 ms |
768 KB |
b24 |
AC |
5 ms |
768 KB |
b25 |
AC |
5 ms |
768 KB |
b26 |
AC |
5 ms |
768 KB |
b27 |
AC |
61 ms |
768 KB |
b28 |
AC |
5 ms |
768 KB |
b29 |
AC |
5 ms |
768 KB |
b30 |
AC |
5 ms |
768 KB |
b31 |
AC |
5 ms |
768 KB |
b32 |
AC |
17 ms |
768 KB |
b33 |
AC |
5 ms |
768 KB |
b34 |
AC |
253 ms |
768 KB |
b35 |
AC |
2 ms |
768 KB |
b36 |
AC |
2 ms |
768 KB |
b37 |
AC |
2 ms |
768 KB |
b38 |
AC |
5 ms |
768 KB |
b39 |
AC |
13 ms |
768 KB |
b40 |
AC |
58 ms |
768 KB |
b41 |
AC |
3 ms |
768 KB |
b42 |
AC |
24 ms |
768 KB |
b43 |
AC |
2 ms |
768 KB |
b44 |
AC |
65 ms |
768 KB |
b45 |
AC |
63 ms |
768 KB |
b46 |
AC |
157 ms |
768 KB |
b47 |
AC |
141 ms |
768 KB |
b48 |
AC |
144 ms |
768 KB |
b49 |
AC |
64 ms |
768 KB |
b50 |
AC |
270 ms |
768 KB |
b51 |
AC |
270 ms |
768 KB |
b52 |
AC |
55 ms |
768 KB |
b53 |
AC |
59 ms |
768 KB |
b54 |
AC |
33 ms |
768 KB |
b55 |
AC |
56 ms |
768 KB |
b56 |
AC |
49 ms |
768 KB |
b57 |
AC |
84 ms |
768 KB |
b58 |
AC |
269 ms |
768 KB |
b59 |
AC |
83 ms |
768 KB |
b60 |
AC |
113 ms |
768 KB |
b61 |
AC |
112 ms |
768 KB |
b62 |
AC |
66 ms |
768 KB |
b63 |
AC |
69 ms |
768 KB |