제출 #1361000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361000		Jawad_Akbar_JJ	도로 폐쇄 (APIO21_roads)	C++17	12 / 100	22 ms	6200 KiB

roads

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define ll long long
const int N = 1<<17;
ll dp[N][2];

vector<ll> sub1(int n, vector<int> U, vector<int> V, vector<int> W){
	sort(rbegin(W), rend(W));

	vector<ll> Ans(n, 0);
	for (int i : W)
		Ans[0] += i;
	for (int i=1;i<=W.size();i++)
		Ans[i] = Ans[i-1] - W[i-1];
	return Ans;
}

vector<ll> sub2(int n, vector<int> U, vector<int> V, vector<int> W){
	vector<ll> Ans(n, 0);
	for (int i : W)
		Ans[0] += i;

	for (int i=1;i<n;i++){
		dp[i][1] = dp[i-1][0];
		dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + W[i-1];
	}
	Ans[1] = min(dp[n-1][0], dp[n-1][1]);
	return Ans;
}

vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W){
	bool t = 1;
	for (int i=0;i<n-1;i++)
		t &= U[i] == 0;

	if (t)
		return sub1(n, U, V, W);
	return sub2(n, U, V, W);
}

• 서브태스크 1: 5 / 5
• 서브태스크 2: 7 / 7
• 서브태스크 3: 0 / 14
• 서브태스크 4: 0 / 10
• 서브태스크 5: 0 / 17
• 서브태스크 6: 0 / 25
• 서브태스크 7: 0 / 22