제출 #1247170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247170		julia_08	Džumbus (COCI19_dzumbus)	C++20	110 / 110	34 ms	25156 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 1e3 + 10;

const ll INF = 1e18;

int d[MAXN], marc[MAXN], sub[MAXN];

ll dp[MAXN][MAXN][3];

vector<int> adj[MAXN];

int n, m; 

void init(int v){

  sub[v] = 1;

  for(int i=0; i<=n; i++) dp[v][i][0] = dp[v][i][1] = dp[v][i][2] = INF;

  dp[v][0][0] = 0;
  dp[v][0][2] = d[v];

}

void merge(int u, int v){

  for(int i=sub[v]; i>=0; i--){
    for(int j=sub[u]; j>=0; j--){
        
      dp[v][i + j][0] = min(dp[v][i + j][0], dp[v][i][0] + min({dp[u][j][0], dp[u][j][1], dp[u][j][2]}));

      dp[v][i + j][1] = min(dp[v][i + j][1], dp[v][i][1] + min({dp[u][j][0], dp[u][j][1], dp[u][j][2]}));

      dp[v][i + j + 1][1] = min(dp[v][i + j + 1][1], min(dp[v][i][1], dp[v][i][2]) + dp[u][j][2]);
      dp[v][i + j + 1][1] = min(dp[v][i + j + 1][1], dp[v][i][2] + min(dp[u][j][1], dp[u][j][2]));

      dp[v][i + j + 2][1] = min(dp[v][i + j + 2][1], dp[v][i][2] + dp[u][j][2]);

      dp[v][i + j][2] = min(dp[v][i + j][2], dp[v][i][2] + dp[u][j][0]);

    }
  }

  sub[v] += sub[u];

}

void dfs(int v){

  marc[v] = 1;

  init(v);

  for(auto u : adj[v]){
    if(!marc[u]){
      dfs(u);
      merge(u, v);
    }
  }

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;

  for(int i=1; i<=n; i++) cin >> d[i];

  while(m--){
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  vector<int> roots;

  for(int i=1; i<=n; i++){
    if(!marc[i]){
      adj[0].push_back(i);    
      dfs(i);
    }
  }

  init(0);

  for(auto v : adj[0]) merge(v, 0);

  int q; cin >> q;

  for(int i=1; i<=q; i++){

    int s; cin >> s;

    int l = 0, r = n;

    while(l < r){
      int m = l + (r - l + 1) / 2;
      if(dp[0][m][0] <= s) l = m;
      else r = m - 1;
    }

    cout << l << "\n";

  }


  return 0;
}

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