Submission #969669

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
969669	2024-04-25 12:58:26	europium	Road Closures (APIO21_roads)	C++17	7 / 100	41 ms	11204 KiB

roads

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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]
    dp[0][0] = 0;
    dp[0][1] = w[0];
    for (int i = 1; i < n - 1; i ++) {
        dp[i][0] = dp[i-1][1];
        dp[i][1] = w[i] + min(dp[i-1][1], dp[i-1][0]);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22