#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=1001;
const ll MAXK=1000001;
const ll INF = 1e13;
const ll MOD = 1e9+7;
vi dp1[MAXN]; // off
vi dp2[MAXN]; // on
vi dp3[MAXN]; // island
ll sub[MAXN];
ll A[MAXN];
vi V[MAXN];
ll N,M,a,b;
ll dpx[MAXN][2];
ll dpy[MAXN][2];
ll dpz[MAXN][2];
void db(ll x){
return;
cerr<<"Node "<<x<<'\n';
cerr<<"OFF: ";for(auto i:dp1[x])cout<<i<<' ';cout<<'\n';
cerr<<"ISLAND: ";for(auto i:dp2[x])cout<<i<<' ';cout<<'\n';
cerr<<"ON: ";for(auto i:dp3[x])cout<<i<<' ';cout<<'\n';
cerr<<'\n';
}
void dfs(ll x,ll p){
// cerr<<"Dfs "<<x<<' '<<p<<'\n';
sub[x]=1;
if(SZ(V[x])==1&&p!=-1){
dp1[x].pb(0);dp1[x].pb(INF);
dp2[x].pb(INF);dp2[x].pb(A[x]);
dp3[x].pb(INF);dp3[x].pb(INF);
db(x);
return;
}
vi child;
for(auto v:V[x])if(v!=p)child.pb(v);
for(auto i:child){dfs(i,x);sub[x]+=sub[i];}
// first we dp to find the optimal for OFF
for(ll i=0;i<=sub[x];++i)dpx[i][0]=dpx[i][1]=INF;
ll T=0;
dpx[0][0]=0;
ll t=1;
for(auto i:child){
// cerr<<"Child "<<i<<' '<<sub[i]<<' '<<SZ(dp3[i])<<'\n';
for(ll i=0;i<=T+sub[i];++i)dpx[i][t]=INF;
for(ll c=0;c<=sub[i];++c){
ll val=c;
ll cst=min({dp1[i][c],dp3[i][c]});
for(ll i=0;i<=T;++i){
ll n=i+val;
ll w=cst+dpx[i][1-t];
dpx[n][t]=min(w,dpx[n][t]);
}
}
T+=sub[i];
t=1^t;
}
for(ll i=0;i<=T;++i)dp1[x].pb(dpx[i][t^1]);
dp1[x].pb(INF);
// dp to find the optimal for ON
for(ll i=0;i<=sub[x];++i)dpx[i][0]=dpx[i][1]=INF;
for(ll i=0;i<=sub[x];++i)dpy[i][0]=dpy[i][1]=INF;
T=0;t=1;
dpx[0][0]=0; // dpx[0] means not on
assert(SZ(child)==1);
for(auto i:child){
for(ll i=0;i<=T+sub[i];++i)dpx[i][t]=dpy[i][t]=INF;
for(ll c=0;c<=sub[i];++c){
ll val=c;
ll csa=dp1[i][c];
ll csb=min(dp2[i][c],dp3[i][c]);
for(ll i=0;i<=T;++i){ // OFF to OFF
ll n=i+val;
ll w=csa+dpx[i][1^t];
dpx[n][t]=min(w,dpx[n][t]);
}
for(ll i=0;i<=T;++i){ // OFF to ON
ll n=i+val;
ll w=csb+dpx[i][1^t];
dpy[n][t]=min(w,dpy[n][t]);
}
for(ll i=0;i<=T;++i){ // ON to ON
ll n=i+val;
ll w=min(csa,csb)+dpy[i][1^t];
// cerr<<i<<" to "<<n<<' '<<dpy[i][1-t]<<' '<<w<<'\n';
dpy[n][t]=min(w,dpy[n][t]);
}
}
T+=sub[i];
t=1^t;
}
dp2[x].pb(INF);dp3[x].pb(INF);
for(ll i=0;i<=T;++i)dp3[x].pb(dpy[i][t^1]+A[x]); // ON
for(ll i=0;i<=T;++i)dp2[x].pb(dpx[i][t^1]+A[x]); // ISLAND
db(x);
}
ll res[MAXN];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>N>>M;
for(ll i=1;i<=N;++i)cin>>A[i];
for(ll i=0;i<M;++i){
cin>>a>>b;V[a].pb(b);V[b].pb(a);
}
for(ll i=0;i<=N;++i)dpz[i][0]=dpz[i][1]=INF;
ll T=0;
dpz[0][0]=0;
ll t=1;
for(int x=1;x<=N;++x){
if(SZ(dp1[x]))continue;
dfs(x,-1);
vi tm;
for(int i=0;i<=sub[x];++i)tm.pb(min(dp1[x][i],dp3[x][i]));
for(int i=sub[x]-1;i>=0;--i)tm[i]=min(tm[i],tm[i+1]);
for(ll i=0;i<=T+sub[x];++i)dpz[i][t]=INF;
for(ll c=0;c<=sub[x];++c){
ll val=c;
ll cst=tm[c];
for(ll i=0;i<=T;++i){
ll n=i+val;
ll w=cst+dpz[i][1^t];
dpz[n][t]=min(w,dpz[n][t]);
}
}
T+=sub[x];
// cerr<<t<<'\n';
// for(int i=0;i<=T;++i)cout<<dpz[i][t]<<' ';cout<<'\n';
t=1^t;
}
for(int i=0;i<=N;++i)res[i]=dpz[i][t^1];
cin>>a;while(a--){
cin>>b;
ll t=ub(res,res+N+1,b)-res-1;
cout<<t<<'\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
34 ms |
20792 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
34 ms |
20792 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
34 ms |
20792 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
