Submission #1299291

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

dzumbus

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const ll inf = 1e18;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m; cin >> n >> m;
    vector<ll>d(n+1); for(int i=1;i<=n;i++) cin >> d[i];
    vector<vector<int>>adj(n+1);
    for(int i=0;i<m;i++){
        int a,b; cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    vector<int>order;
    if(n==1){
        order.pb(1);
    }else{
        int inic = 1;
        for(int i=1;i<=n;i++)
            if(adj[i].size()<=1){
                inic = i;
                break;
            }
        order.reserve(n);
        vector<int>vis(n+1,0);
        int cur = inic, prev = -1;
        while(true){
            order.pb(cur);
            vis[cur] = 1;
            int next = -1;
            for(int v: adj[cur]){
                if(v==prev) continue;
                next = v;
                break;
            }
            if(next == -1) break;
            prev = cur;
            cur = next;
        }
    }
    vector<ll>cost(n+1,0);
    for(int i=0;i<n;i++) cost[i+1] = d[order[i]];
    vector<vector<array<ll,3>>>dp(n+1,vector<array<ll,3>>(n+1));
    for(int i=0;i<=n;i++)
        for(int k=0;k<=n;k++)
            dp[i][k][0] = dp[i][k][1] = dp[i][k][2] = inf;
    dp[0][0][0] = 0;
    for(int i=0;i<n;i++){
        for(int k=0;k<=n;k++){
            for(int s =0;s<3;s++){
                ll cur = dp[i][k][s];
                if(cur == inf) continue;
                dp[i+1][k][0] = min(dp[i+1][k][0] , cur);
                ll nc = cur + cost[i+1];
                if(s==0){
                    dp[i+1][k][1] = min(dp[i+1][k][0], cur);
                }else if(s==1){
                    if(k+2<=n) dp[i+1][k+2][2] = min(dp[i+1][k+2][2], nc);
                }else{
                    if(k+1 <= n)dp[i+1][k+1][2] = min(dp[i+1][k+1][2], nc);
                }
            }
        }
    }
    vector<ll>minc(n+1,inf);
    for(int k=0;k<=n;k++){
        for(int s=0;s<3;s++){
            minc[k] = min(minc[k], dp[n][k][s]);
        }
    }
    for(int k=1;k<=n;k++)
        if(minc[k] < minc[k-1])
            minc[k] = minc[k-1];
    int q; cin >> q;
    while(q--){
        ll s; cin >> s;
        int lo =0 , hi = n, ans = 0;
        while(lo <= hi){
            int mid = (lo+hi)/2;
            if(minc[mid]<=s){
                ans = mid;
                lo = mid+1;
            }else  hi = mid-1;
        }
        cout<<ans<<'\n';
    }
}

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