This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll INF = 1000000000000000000LL;
const int N = 1000;
ll cost[2][N+5];
ll val[N+5];
ll dp[N+5][N+5][2];
ll dole[2][N+5];
ll pov[2][N+5];
int sz[N+5];
bool visited[N+5];
vector <int> graf[N+5];
int n;
void dfs(int v, int p){
visited[v] = 1;
sz[v] = 1;
for(auto c : graf[v]){
if(c == p) continue;
dfs(c, v);
sz[v] += sz[c];
}
for(int i=0; i<=sz[v]; i++) dp[v][i][0] = dp[v][i][1] = INF;
int tsz = 1;
for(int i=1; i<=sz[v]; i++) dole[1][i] = INF;
for(int i=0; i<=sz[v]; i++) pov[1][i] = INF;
for(auto c : graf[v]){
if(c == p) continue;
for(int i=0; i<=sz[v]; i++){
dole[0][i] = dole[1][i];
pov[0][i] = pov[1][i];
}
for(int i=0; i<=sz[c]; i++){
for(int j=0; j<=tsz; j++){
dole[1][i+j] = min(dole[1][i+j], dole[0][j] + min(dp[c][i][0], dp[c][i][1]));
pov[1][i+j+2] = min(pov[1][i+j+2], dole[0][j] + val[v] + val[c] + dp[c][i][0]);
pov[1][i+j+1] = min(pov[1][i+j+1], dole[0][j] + val[v] + dp[c][i][1]);
pov[1][i+j] = min(pov[1][i+j], pov[0][j] + min(dp[c][i][0], dp[c][i][1]));
pov[1][i+j+1] = min(pov[1][i+j+1], pov[0][j] + val[c] + dp[c][i][0]);
}
}
tsz += sz[c];
}
for(int i=0; i<=sz[v]; i++){
dp[v][i][0] = dole[1][i];
dp[v][i][1] = pov[1][i];
}
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int m;
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> val[i];
for(int i=1; i<=m; i++){
int a, b;
cin >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
}
for(int i=1; i<=n; i++) cost[1][i] = INF;
int tsz = 0;
for(int i=1; i<=n; i++){
if(!visited[i]){
dfs(i, 0);
for(int j=1; j<=n; j++) cost[0][j] = cost[1][j];
for(int j=1; j<=sz[i]; j++){
for(int k=0; k<=tsz; k++){
cost[1][j+k] = min(cost[1][j+k], cost[0][k] + min(dp[i][j][1], dp[i][j][0]));
}
}
tsz += sz[i];
}
}
for(int i=n-1; i>=1; i--) cost[1][i] = min(cost[1][i], cost[1][i+1]);
int qrs;
cin >> qrs;
while(qrs--){
ll d;
cin >> d;
int l = 1, r = n, res = 0;
while(l <= r){
int mid = (l+r)/2;
if(cost[1][mid] <= d){
res = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << res << "\n";
}
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... |