# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
198132 | ZwariowanyMarcin | Džumbus (COCI19_dzumbus) | C++14 | 115 ms | 35124 KiB |
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>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define LL long long
#define ld double
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define boost cin.tie(0), ios_base::sync_with_stdio(0);
using namespace std;
const int nax = 1010;
const LL INF = 1e18;
void mini(LL &a, LL b) {
a = min(a, b);
}
int n, m;
int cost[nax];
int a, b;
int q;
vector <int> v[nax];
bool odw[nax];
LL dp[nax][nax][2][2];
LL dp2[nax][2][2];
int siz[nax];
void dfs(int u, int p) {
odw[u] = 1;
siz[u] = 1;
dp[u][0][0][0] = 0;
dp[u][1][1][1] = cost[u];
for (auto it : v[u])
if (it != p) {
dfs(it, u);
for (int i = 0; i <= n; ++i)
for (int j = 0; j < 2; ++j)
for (int g = 0; g < 2; ++g)
dp2[i][j][g] = INF;
for (int i = 0; i <= siz[u]; ++i)
for (int j = 0; j <= siz[it]; ++j)
for (int x = 0; x < 2; ++x)
for (int y = 0; y < 2; ++y)
for (int z = 0; z < 2; ++z)
for (int g = 0; g < 2; ++g) {
int s = i + j - (z == 1 && g == 1 && x == 0);
int p = (y == 1 && z == 0);
mini(dp2[s][x][p], dp[u][i][x][y] + dp[it][j][z][g]);
}
siz[u] += siz[it];
for (int i = 0; i <= siz[u]; ++i)
for (int j = 0; j < 2; ++j)
for (int g = 0; g < 2; ++g)
dp[u][i][j][g] = dp2[i][j][g];
}
}
LL ans[nax];
LL ans2[nax];
vector <pair<LL, int>> vec;
int pref[nax];
int main() {
scanf ("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf ("%d", cost + i);
for (int i = 1; i <= m; ++i) {
scanf ("%d%d", &a, &b);
v[a].pb(b);
v[b].pb(a);
}
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= n; ++j)
for (int k = 0; k < 2; ++k)
for (int f = 0; f < 2; ++f)
dp[i][j][k][f] = INF;
for (int i = 1; i <= n; ++i)
ans[i] = INF;
for (int i = 1; i <= n; ++i)
if (!odw[i]) {
dfs(i, 0);
for (int j = 0; j <= n; ++j)
ans2[j] = ans[j];
for (int j = 2; j <= siz[i]; ++j)
for (int g = n - j; 0 <= g; --g)
ans2[g + j] = min(ans2[g + j], ans[g] + min(dp[i][j][1][0], dp[i][j][0][0]));
for (int j = 0; j <= n; ++j)
ans[j] = ans2[j];
}
for (int i = 0; i <= n; ++i)
vec.pb({ans[i], i});
sort(vec.begin(), vec.end());
for (int i = 0; i < ss(vec); ++i) {
if (i) pref[i] = pref[i - 1];
pref[i] = max(pref[i], vec[i].se);
}
scanf ("%d", &q);
for (int i = 1; i <= q; ++i) {
scanf ("%d", &a);
int ind = (int) (upper_bound(vec.begin(), vec.end(), mp(1LL * a, n + 1)) - vec.begin()) - 1;
printf ("%d\n", pref[ind]);
}
return 0;
}
Compilation message (stderr)
# | 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... |