제출 #1293796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293796		ayxanesedzade10	Paprike (COI18_paprike)	C++20	24 / 100	66 ms	4176 KiB

paprike

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define ld long double
using namespace std;
const ll sz=1e5+100;
vector<ll>v[sz];
vector<array<ll,2>>edges;
ll used[sz],h[sz],cnt;
void dfs(ll u)
{
    used[u]=1;
    cnt+=h[u];
    for(auto to:v[u]){
        if(used[to]) continue;
        dfs(to);
    }
}
int main()
{
    ll n,k;cin>>n>>k;
    ll pre[n+5];
    pre[0]=0;
    for(int i=1;i<=n;i++){
        cin>>h[i];
        pre[i]=pre[i-1]+h[i];
    }
    for(int i=1;i<n;i++){
        ll a,b;cin>>a>>b;
        edges.pb({a,b});
    }
    ll ans=n-1;
    if(n<=15){
    for(int mask=0;mask<(1<<(n-1));mask++){
        vector<array<ll,2>>v1;
        ll num=n-1;
        for(int j=0;j<n-1;j++){
            if(mask&(1<<j)){
                v1.pb({edges[j][0],edges[j][1]});num--;
            }
        }
        for(int i=0;i<=n;i++){
            used[i]=0;v[i].clear();
        }
        for(auto [to1,to2]:v1){
            v[to1].pb(to2);
            v[to2].pb(to1);
        }
        ll ok=0;
        for(int i=1;i<=n;i++){
            if(used[i]==0){
                cnt=0;
                dfs(i);
                if(cnt>k){ok=1;break;}
            }
        }
        if(ok==0){
            ans=min(ans,num);
        }
    }
    cout<<ans<<endl;}
    else{
        ll last1=0,cnt1=0;
    for(int i=1;i<=n;i++){
        if(pre[i]-last1>k){
            last1=pre[i-1];
            cnt1++;
        }
    }
    cout<<cnt1<<endl;
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49