# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
710483 | irmuun | 도로 폐쇄 (APIO21_roads) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "roads.h"
using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define PI 3.1415926535897932384626433
#define all(s) s.begin(),s.end()
const ll mod=1000000007,mod1=998244353,INF=1e18,MAX=1e9;
vector<ll> minimum_closure_costs(int n,vector<int>u,vector<int>v,vector<int>w){
int cnt=0;
for(int i=0;i<n-1;i++){
if(u[i]==0){
cnt++;
}
}
if(cnt==n-1){
sort(all(w));
ll cur=0;
for(ll i=0;i<n;i++){
cur+=w[i];
}
vector<ll>ans;
for(ll i=n-1;i>=0;i--){
cur-=w[i];
ans.pb(cur);
}
return ans;
}
vector<ll>ans(n,0);
ll cur=0;
for(int i=0;i<n-1;i++){
cur+=w[i];
}
v[0]=cur;
ll dp[n+5];
dp[0]=0;
dp[1]=w[0];
for(int i=2;i<n;i++){
dp[i]=min(dp[i-1],dp[i-2])+w[i-1];
}
ans[1]=min(dp[i-1],dp[i-2]);
return ans;
}