#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#warning Check Integer OverFlow
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORd(i,a,b) for(int i=a;i>=b;i--)
#define trav(a,b) for(auto a:b)
#define sz(a) a.size()
#define maxs(a,b) if(b>a)a=b
#define mins(a,b) if(b<a)a=b
#ifdef LOCAL
#define dbg(x) cerr<<"["<<#x<<":"<<x<<"] "
#define dbg2(a,b) dbg(a);dbg(b)
#define dbg3(a,b,c) dbg2(a,b);dbg(c)
#define dln cerr << ln
#else
#define dbg(x) 0
#define dbg2(a,b) 0
#define dbg3(a,b,c) 0
#define dln 0
#endif
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (((a)/(__gcd(a,b))) * b)
#define print(arr) for(auto it = arr.begin();it < arr.end();it ++){cout << *it << " ";}cout << ln;
#define all(a) (a).begin(), (a).end()
#define vi vector<int>
#define v vector
#define p pair
#define pii p<int,int>
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define ln "\n"
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
ll modF=1e9+7;
template<class T> using iset = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
/*OUTPUT
*/
#define maxn 1000
ll N, M, d[maxn], ind[maxn], ans[200000];
vector<ll> adj[maxn], arr;
void dfs(int x,int pr){
arr.pb(d[x]);
trav(e,adj[x]){
if(e != pr)dfs(e,x);
}
}
void solve(){
cin >> N >> M;
FOR(i,0,N) cin >> d[i];
FOR(i,0,M){
int x,y;
cin >> x >> y;
x --;y --;
adj[x].pb(y);
adj[y].pb(x);
ind[x] ++;ind[y] ++;
}
int start = 0;FOR(i,0,N)if(ind[i] < 2)start = i;
dfs(start,-1);
int Q;cin >> Q;
vector<pair<ll,int>> queries;
FOR(i,0,Q){
int x;
cin >> x;
queries.pb(mk(x,i));
}
sort(all(queries));
int ptr = 0;
ll pr = 0;
int an = 0;
trav(x,queries){
if(ptr < N and pr + arr[ptr] <= x.f){
an ++;
ptr ++;
pr += arr[ptr];
}
if(an >= 2)
maxs(ans[x.s], an);
}
ptr = N - 1, pr = an = 0;
trav(x,queries){
if(ptr >= 0 and pr + arr[ptr] <= x.f){
an ++;
ptr --;
pr += arr[ptr];
}
if(an >= 2)
maxs(ans[x.s], an);
}
if(N >= 2){
an = 0,pr = arr[0] + arr[N - 1];
int p = 1, q = N - 2;
trav(x,queries){
if(p <= q and pr + min(arr[p],arr[q]) <= x.f){
an ++;
pr += min(arr[p],arr[q]);
if(arr[p] < arr[q])p ++;
else q --;
}
int crr = an;
if(p > 1)crr ++;
if(q < N - 2)crr ++;
maxs(ans[x.s],crr);
}
}
FOR(i,0,Q){
cout << ans[i] << '\n';
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t = 1;
// cin >> t;
while(t --){
solve();
}
}
Compilation message
dzumbus.cpp:4:2: warning: #warning Check Integer OverFlow [-Wcpp]
4 | #warning Check Integer OverFlow
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
7408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
