Submission #491555

#	Time	Username	Problem	Language	Result	Execution time	Memory
491555		Croco	Džumbus (COCI19_dzumbus)	C++17	110 / 110	53 ms	26820 KiB

dzumbus

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

using namespace std;

const int N = 1e3 + 5;

int n,m;
vector<int> g[N];
int dp[N][N][3];
bool vis[N];
int cost[N];
int sz[N];
int inf = 1e9 + 5;

void dfs(int v)
{
    vis[v] = 1;
    dp[v][0][0] = 0;
    dp[v][1][1] = cost[v];
    sz[v] = 1;
    for(auto x : g[v])
    {
        if(vis[x])
            continue;
        dfs(x);
        for(int i=sz[v];i>=0;i--)
        {
            for(int j=0;j<=sz[x];j++)
            {
                dp[v][i+j][0] = min(dp[v][i+j][0] , dp[v][i][0] + min(dp[x][j][0] , dp[x][j][2]));
                dp[v][i+j][1] = min(dp[v][i+j][1] , dp[v][i][1] + min(dp[x][j][0] , dp[x][j][2]));
                dp[v][i+j][2] = min(dp[v][i+j][2] , dp[v][i][1] + min(dp[x][j][1] , dp[x][j][2]));
                dp[v][i+j][2] = min(dp[v][i+j][2] , dp[v][i][2] + min({dp[x][j][1],dp[x][j][0],dp[x][j][2]}));
            }
        }
        sz[v] += sz[x];
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>cost[i];
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int tot = 0;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = inf;
    dp[0][0][0] = 0;
    for(int x=1;x<=n;x++)
    {
        if(vis[x])
            continue;
        dfs(x);
        int v = 0;
        for(int i=tot;i>=0;i--)
        {
            for(int j=0;j<=sz[x];j++)
            {
                dp[v][i+j][0] = min(dp[v][i+j][0] , dp[v][i][0] + min(dp[x][j][0] , dp[x][j][2]));
            }
        }
        tot += sz[x];
    }
    for(int i=n-1;i>=0;i--)
        dp[0][i][0] = min(dp[0][i][0] , dp[0][i+1][0]);
    int q;
    cin>>q;
    while(q--)
    {
        int val;
        cin>>val;
        int best = 0,low = 0;
        int high = n;
        while(low <= high)
        {
            int mid = (low + high)/2;
            if(dp[0][mid][0] <= val)
            {
                best = mid;
                low = mid+1;
            }
            else
                high = mid-1;
        }
        cout << best << "\n";
    }
}

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