Submission #1023042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023042		anarch_y	Džumbus (COCI19_dzumbus)	C++17	110 / 110	46 ms	17748 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define int long long

vector<int> combine(vector<int> a, vector<int> b){
    vector<int> c(sz(a)+sz(b)-1, 1e16);
    for(int i=0; i<sz(a); i++){
        for(int j=0; j<sz(b); j++){
            c[i+j] = min(c[i+j], a[i]+b[j]);
        }
    }
    return c;
}

vector<int> find_min(vector<int> a, vector<int> b){
    vector<int> c(sz(a));
    for(int i=0; i<sz(a); i++){
        c[i] = min(a[i], b[i]);
    }
    return c;
}

const int maxn = 1001;
vector<int> adj[maxn];
vector<int> dp[maxn][4];
int vis[maxn], D[maxn];

void dfs(int s, int p){
    vis[s] = 1;
    dp[s][0] = {0, (int)1e16};
    dp[s][1] = {(int)1e16, (int)1e16};
    dp[s][2] = {(int)1e16, D[s]};
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s);
        dp[s][0] = combine(dp[s][0], dp[u][3]);
        vector<int> a[5];
        a[0] = combine(dp[s][1], dp[u][0]);
        a[1] = combine(dp[s][1], dp[u][1]);
        a[2] = combine(dp[s][1], dp[u][2]);
        a[3] = combine(dp[s][2], dp[u][1]);
        a[4] = combine(dp[s][2], dp[u][2]);
        dp[s][1] = a[0];
        for(int i=1; i<5; i++){
            dp[s][1] = find_min(dp[s][1], a[i]);
        }
        dp[s][2] = combine(dp[s][2], dp[u][0]);
    }
    dp[s][3] = dp[s][0];
    dp[s][3] = find_min(dp[s][3], dp[s][1]);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> D[i];
    for(int i=0; i<m; i++){
        int a, b; cin >> a >> b;
        adj[a].pb(b); adj[b].pb(a);
    }
    vector<int> v;
    for(int i=1; i<=n; i++){
        if(!vis[i]){
            dfs(i, 0);
            v.pb(i);
        }
    }
    vector<int> ans = {0};
    for(auto i: v){
        ans = combine(ans, dp[i][3]);
    }
    int q; cin >> q;
    while(q--){
        int r; cin >> r;
        int L = 2, R = n;
        int t = 0;
        while(L <= R){
            int mid = (L+R)/2;
            if(ans[mid] <= r){
                t = mid;
                L = mid+1;
            }
            else R = mid-1;
        }
        cout << t << "\n";
    }
}

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