Submission #1119166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119166		LonlyR	Džumbus (COCI19_dzumbus)	C++17	110 / 110	390 ms	34996 KiB

dzumbus

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 1e3 + 5;
int n, m, q;
int val[maxn], vis[maxn], take[maxn], sz[maxn], state[maxn];
int dp[maxn][2][maxn][2];
vector<int> adj[maxn];

inline void MIN(int &x, int y)
{
    x = min(x, y);
}

void dfs(int x, int p)
{
    vis[x] = 1;
    sz[x] = (x > 0 ? 1 : n);
    for (int i : adj[x]) if (!vis[i])
        dfs(i, x),
        sz[x] += sz[i];
    memset(dp[x], 0x3f, sizeof dp[x]);
    dp[x][0][0][0] = 0;
    int be = 0, cu = 1;
    for (int u : adj[x]) if (u != p)
    {
        memset(dp[x][cu], 0x3f, sizeof dp[x][cu]);
        int st = state[u];
        for (int i = 0; i <= sz[x]; i++)
            for (int j = 0; j <= sz[u]; j++)
            {
                if (j > i) break;
                MIN(dp[x][cu][i][0], min(dp[u][st][j][0], dp[u][st][j][1]) + dp[x][be][i - j][0]);
                MIN(dp[x][cu][i][1], min(dp[u][st][j][0], dp[u][st][j][1]) + dp[x][be][i - j][1]);
                if (j) MIN(dp[x][cu][i][1], dp[u][st][j - 1][0] + dp[x][be][i - j][1] + val[u]);
                if (x && i - j) MIN(dp[x][cu][i][1], dp[u][st][j][1] + dp[x][be][i - j - 1][0] + val[x]);
                if (x && j && i - j) MIN(dp[x][cu][i][1], dp[u][st][j - 1][0] + dp[x][be][i - j - 1][0] + val[x] + val[u]);
            }
        swap(be, cu);
    }
    state[x] = be;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> val[i];
    for (int i = 1, u, v; i <= m; i++)
        cin >> u >> v,
        adj[u].emplace_back(v),
        adj[v].emplace_back(u);
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, i),
            adj[0].emplace_back(i);
    dfs(0, 0);
    take[n + 1] = 1e18;
    for (int i = n; i >= 2; i--)
    {
        int st = state[0];
        take[i] = min({take[i + 1], dp[0][st][i][0], dp[0][st][i][1]});
    }
    cin >> q;
    while (q--)
    {
        int x; cin >> x;
        int ans = upper_bound(take + 2, take + n + 1, x) - take - 1;
        cout << (ans <= 1 ? 0 : ans) << "\n";
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30