제출 #969698

#제출 시각아이디문제언어결과실행 시간메모리
969698europium도로 폐쇄 (APIO21_roads)C++17
7 / 100
37 ms9052 KiB
#include "roads.h" #include <vector> #include <bits/stdc++.h> using namespace std; using ll = long long; vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> w) { vector<ll> ans(n, ll(0)); // chain // k = 0 --> close all roads // k = 1 --> DP solution // k >= 2 --> don't need to close any road, 0 ll cost = accumulate(w.begin(), w.end(), ll(0)); ans[0] = cost; vector<vector<ll>> dp(n - 1, vector<ll>(2, (ll)0)); // dp[i][j] // i - current index // j - 0 or 1. 1 means block the current road. 0 means don't block. dp[0][0] = 0; dp[0][1] = w[0]; for (int i = 1; i < n - 1; i ++) { // current index is unblocked, which means that the previous road segment must be blocked // because we cannot have 2 consecutive unblocked segments dp[i][0] = dp[i-1][1]; // current index is blocked. The previous road segment can be blocked or unblocked. dp[i][1] = w[i] + min(dp[i-1][1], dp[i-1][0]); } ans[1] = min(dp[n-2][0], dp[n-2][1]); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...