Submission #1081147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081147		pawned	Road Closures (APIO21_roads)	C++17	7 / 100	34 ms	8144 KiB

roads

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "roads.h"

vi minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W_g) {
	vector<ll> W;
	for (ll x : W_g)
		W.pb(x);
	ll total = 0;
	for (ll x : W)
		total += x;
	vi ans(N, 0);
	ans[0] = total;
	// compute ans[1]
	vi dp1(N, 1e18);	// for computing ans[1]
	// dp1[i]: min cost so no double line up to i (inclusive)
	// must remove previous line
	vi dp2(N, 1e18);
	// dp2[i]: same, but must not remove prev line
	dp1[0] = 1e18;
	dp2[0] = 0;
	dp1[1] = W[0];
	dp2[1] = 0;
	for (int i = 2; i < N; i++) {
		dp1[i] = min(dp1[i - 1], dp2[i - 1]) + W[i - 1];
		dp2[i] = dp1[i - 1];
	}
/*	cout<<"dp1: ";
	for (ll x : dp1)
		cout<<x<<" ";
	cout<<endl;
	cout<<"dp2: ";
	for (ll x : dp2)
		cout<<x<<" ";
	cout<<endl;*/
	ans[1] = min(dp1[N - 1], dp2[N - 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