제출 #1263509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263509		DangKhoizzzz	Džumbus (COCI19_dzumbus)	C++20	0 / 110	17 ms	32068 KiB

dzumbus

#include<bits/stdc++.h>
#define pii pair <int , int>
#define fi first
#define se second
#define arr3 array <int , 3>
#define int long long

using namespace std;

const int maxn = 1e3 + 7;
const int INF = 1e18;

bool vis[maxn];
int n , m  , dp[2][2][maxn][maxn], sz[maxn], d[maxn] , ans[maxn];
vector <int> g[maxn];

void dfs(int u , int p)
{
    vis[u] = 1;
    sz[u] = 1;
    dp[1][0][u][1] = d[u];
    dp[0][1][u][0] = 0;

    for(int v: g[u])
    {
        if(v == p) continue;
        dfs(v , u);
        for(int a = sz[u]; a >= 0; a--)
        {
            for(int b = sz[v]; b >= 1; b--)
            {
                dp[0][1][u][a+b] = min(dp[0][1][u][a+b] , dp[0][1][u][a] + min(dp[0][1][v][b] , dp[1][1][v][b]));
                dp[1][0][u][a+b] = min(dp[1][0][u][a+b] , dp[1][0][u][a] + dp[0][1][v][b]);
                dp[1][1][u][a+b] = min(dp[1][1][u][a+b] , dp[1][1][u][a] + min({dp[0][1][v][b] , dp[1][0][v][b] , dp[1][1][v][b]}));
                dp[1][1][u][a+b] = min(dp[1][1][u][a+b] , dp[1][0][u][a] + min(dp[1][0][v][b] , dp[1][1][v][b]));
            }
        }
        sz[u] += sz[v];
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> d[i];
    for(int i = 1; i <= m; i++)
    {
        int u , v; 
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            for(int a = 0; a < 2; a++)
            {
                for(int b = 0; b < 2; b++) dp[a][b][i][j] = INF;
            }
        }
        ans[i] = INF;
    }
    ans[0] = 0;
    ans[1] = INF;

    for(int u = 1; u <= n; u++)
    {
        if(vis[u]) continue;
        dfs(u , u);
        for(int i = n; i >= 2; i--)
        {
            for(int k = 1; k <= i; k++)
            {
                ans[i] = min(ans[i] , ans[i - k] + min(dp[0][1][u][k] , dp[1][1][u][k]));
            }
        }
    }
    int q; cin >> q;
    while(q--)
    {
        int x; cin >> x;
        int s = upper_bound(ans+2 , ans+n+1 , x) - ans - 1;
        s -= (s == 1);
        cout << s << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}
   

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