Submission #1162434

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1162434	2025-03-06 07:46:14	brinton	Road Closures (APIO21_roads)	C++20	0 / 100	24 ms	8516 KiB

roads

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> minimum_closure_costs(int N, vector<int> U,vector<int> V,vector<int> W) {
  // sub1
  vector<long long> ans(N-1,0);
  long long tot = 0;
  for(auto i:W) tot += i;
  ans[0] = tot;
  vector<vector<long long>> dp(N-1,vector<long long>(2));// 0: ntake, 1:take
  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] = min(dp[i-1][0],dp[i-1][1])+W[i];
  }
  ans[1] = min(dp[N-2][0],dp[N-2][1]);
  return ans;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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