제출 #1162436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162436		brinton	Road Closures (APIO21_roads)	C++20	7 / 100	28 ms	9032 KiB

roads

#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,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;
}

• 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