Submission #1299305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299305		aarb_.tomatexd	Džumbus (COCI19_dzumbus)	C++20	0 / 110	20 ms	16184 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const ll inf = 1e15;
const int maxn = 1e3+5;
const int maxq = 2e5+10;
int n,m,q;
int dp[maxn][2][2];
vector<ll>d(maxn);
vector<int>adj[maxn];
ll dpi[maxn][maxn];
ll dpo[maxn][maxn];
int subs[maxn];
pair<int,int>qry[maxq];
int ans[maxq];

ll pdpi[maxn];
ll pdpo[maxn];
void solve(int i, int parent = -1){
    subs[i] = 1;
    if(i!= n){
        for(int j: adj[i]){
            if(j!=parent){
                solve(j,i);
                subs[i] += subs[j];
            }
        }
    }
    for(int k=0;k<=n;k++){
        dpi[i][k] = dpo[i][k] = inf; }
    dpo[i][0] = 0;
    int tot = 0;
    pdpi[0] = inf;
    pdpo[0] = 0;
    for(int j: adj[i]){
        if(j==parent) continue;
        for(int k=0;k<=tot+subs[j]; k++)
            dpi[i][k] = dpo[i][k] = inf;
        for(int a=0;a<=tot;a++){
            for(int b=0;b<=subs[j];b++){
                dpo[i][a+b] = min(
                    dpo[i][a+b],
                    pdpo[a] + min(
                        dpi[j][b],
                        dpo[j][b]
                    )
                );

                dpi[i][a+b] = min(
                    dpi[i][a+b],
                    pdpi[a] + min(
                        dpi[j][b],
                        dpo[j][b]
                    )
                );

                if(b > 0){
                    dpi[i][a+b] = min(
                        dpi[i][a+b],
                        min(
                            pdpo[a],
                            pdpi[a]
                        ) + dpo[j][b-1] + d[j]
                    );
                }
            }
        }
        tot += subs[j];
        for(int k=0;k<=tot;k++){
            pdpi[k] = dpi[i][k];
            pdpo[k] = dpo[i][k];
        }
    }
    for(int k=tot;k>=0;k--)
        dpi[i][k+1] = min(inf, dpi[i][k] + d[i]);
    dpi[i][0] = inf;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i=0;i<n;i++){
        cin >> d[i]; dpi[i][0] = -1;
    }
    for(int i=0;i<m;i++){
        int a,b; cin >> a >> b; a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for(int i=0;i<n;i++){
        if(dpi[i][0] == -1){
            solve(i);
            adj[n].pb(i);
        }
    }
    d[n] = inf;
    solve(n);
    for(int i=n-1;i>=0;i--)
        dpo[n][i] = min(dpo[n][i], dpo[n][i+1]);
    cin >> q;
    for(int i=0;i<q;i++){
        cin >> qry[i].first;
        qry[i].second = i;
    }
    sort(qry,qry+q);
    int ansi = 0;
    for(int i=0;i<q;i++){
        while(ansi < n and dpo[n][ansi+1]  <= qry[i].first)
            ansi++;
        ans[qry[i].second] = ansi;
    }
    for(int i=0;i<q;i++) cout<<ans[i]<<'\n';
}

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