제출 #988752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
988752		noyancanturk	Džumbus (COCI19_dzumbus)	C++17	110 / 110	43 ms	30892 KiB

dzumbus

#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int lim=1100;
const int mod=1e9+7;
    
using pii=pair<int,int>;

int a[lim],sz[lim];
int dp[3][lim][lim];
vector<int>v[lim];

void dfs(int node){
    sz[node]=1;
    for(int i=0;i<lim;i++){
        dp[0][node][i]=dp[1][node][i]=dp[2][node][i]=LLONG_MAX/20;
    }
    dp[0][node][0]=0;
    dp[1][node][0]=a[node];
    for(int ch:v[node]){
        if(sz[ch])continue;
        dfs(ch);
        for(int i=sz[node];0<=i;i--){
            for(int j=0;j<=sz[ch];j++){
                dp[0][node][i+j]=min(dp[0][node][i+j],dp[0][node][i]+min({dp[0][ch][j],dp[1][ch][j],dp[2][ch][j]}));
                dp[1][node][i+j]=min(dp[1][node][i+j],dp[1][node][i]+dp[0][ch][j]);
                dp[2][node][i+j]=min(dp[2][node][i+j],dp[2][node][i]+min({dp[0][ch][j],dp[2][ch][j]}));
                dp[2][node][i+j+1]=min({dp[2][node][i+j+1],dp[2][node][i]+dp[1][ch][j],dp[1][node][i]+dp[2][ch][j]});
                dp[2][node][i+j+2]=min(dp[2][node][i+j+2],dp[1][node][i]+dp[1][ch][j]);
            }
        }
        sz[node]+=sz[ch];
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    vector<int>roots;
    for(int i=1;i<=n;i++){
        if(!sz[i]){
            dfs(i);
            roots.pb(i);
        }
    }
    sz[0]=1;
    for(int i=0;i<=n;i++){
        dp[0][0][i]=LLONG_MAX/10;
    }
    dp[0][0][0]=0;
    for(int ch:roots){
        for(int i=sz[0];0<=i;i--){
            for(int j=0;j<=sz[ch];j++){
                dp[0][0][i+j]=min(dp[0][0][i+j],dp[0][0][i]+min({dp[0][ch][j],dp[1][ch][j],dp[2][ch][j]}));
            }
        }
        sz[0]+=sz[ch];
    }
    for(int i=n-1;0<=i;i--){
        dp[0][0][i]=min(dp[0][0][i],dp[0][0][i+1]);
    }
    int q;
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        int l=1,r=n,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(dp[0][0][mid]<=x){
                ans=mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        cout<<ans<<"\n";
    }
}

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