Submission #1177964

#TimeUsernameProblemLanguageResultExecution timeMemory
1177964mahmudow_mahmytRoad Closures (APIO21_roads)C++20
5 / 100
32 ms4936 KiB
#include<bits/stdc++.h> #define ll long long #define ff first #define ss second #define mxn 100002 #define pb push_back #define yes cout<<"YES"<<endl #define no cout<<"NO"<<endl using namespace std; bool csub1(int &n,vector<int> &u,vector<int> &v,vector<int> &w){ for(int i=0;i<u.size();i++) if(u[i]!=0) return false; return true; } vector<ll> sub1(int &n,vector<int> &u,vector<int> &v,vector<int> &w){ vector<ll> ans(n,0); sort(w.begin(),w.end(),greater<int>()); for(int i=n-2;i>=0;i--){ ans[i]=ans[i+1]; ans[i]+=(ll)w[i]; } return ans; } vector<ll> sub2(int &n,vector<int> &u,vector<int> &v,vector<int> &w){ ll dp[n+2][2]; vector<ll> ans(n,0); dp[0][0]=0,dp[0][1]=0; for(int i=1;i<n;i++){ ans[0]+=w[i]; dp[i][0]=dp[i-1][0]+w[i-1]; dp[i][1]=min(dp[i-1][1],dp[i-1][0]); } ans[0]+=w[0]; 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){ if(csub1(n,u,v,w)) return sub1(n,u,v,w); return sub2(n,u,v,w); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...