This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3", "inline")
#define skillissue <bits/stdc++.h>
#define ultra_mal std
#include skillissue
using namespace ultra_mal;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
#define hash FhashF
const int mod = 1e9 +7, sze = 1E3 +100, inf = LLONG_MAX, P = 1453;
// const int L = 30;
int val[sze];
vector<int> graph[sze];
int md =0;
int r =0;
void dfs(int node,int par=-1,int d=0){
if(d>md){
md=d;
r=node;
}
for(auto v:graph[node]){
if(v!=par){
dfs(v,node,d+1);
}
}
}
vector<int> arr;
void fldfs(int node,int par=-1){
arr.pb(val[node]);
for(auto v:graph[node]){
if(v!=par){
fldfs(v,node);
}
}
}
int dp[sze][2][sze];
/*
dp[i][0][x] = i-ci ni kullanmadan x sumuna gelende max cvb
dp[i][1][x] = i-ci ni kullaninca x sumuna gelende max cvb
*/
int pref[sze];
int mxp[sze];
void cave(){
int n,m;
cin>>n>>m;
arr.pb(0);// 1 indexed
/*
20 +30 : Tree , Chain
N<=100 , O(n^4 ) ? O(n^3 * x ) ? x=1 ?
*/
for(int i=1;i<=n;i++){
cin>>val[i];
}
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
graph[u].pb(v);
graph[v].pb(u);
}
dfs(1);
// cout<<r<<endl;
fldfs(r);
// for(auto v:arr){
// cout<<v<<" ";
// }
// cout<<endl;
// cout<<endl;
int lim = 1000; // 20 bal
dp[0][0][0]=0;
for(int i=1;i<=n;i++){
for(int j=arr[i];j<=lim;j++){
int v = 0,x=dp[i-1][1][j - arr[i]];
if(x==-1){
v=2;
}
else{
if(x>0){
v=x+1;
}
else{
v=-1;
}
}
dp[i][1][j] = v;
dp[i][0][j] = max( dp[i-1][1][j],dp[i-1][0][j] );
mxp[j]=max({dp[i][1][j],dp[i][0][j],mxp[j-1]});
// cout<<i<<" "<<1<<" "<<j<<" "<<dp[i][1][j]<<endl;
// cout<<i<<" "<<0<<" "<<j<<" "<<dp[i][0][j]<<endl;
}
}
// for(int i=1;i<=10;i++){
// cout<<mxp[i]<<" ";
// }
// cout<<endl;
int q;
cin>>q;
while(q--){
int s;
cin>>s;
cout<<mxp[s]<<endl;
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int tt = 1;
// cin>>tt;
while(tt--){
cave();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |