Submission #1187411

#TimeUsernameProblemLanguageResultExecution timeMemory
1187411vitoNestabilnost (COI23_nestabilnost)C++17
0 / 100
57 ms12564 KiB
#include <bits/stdc++.h> using namespace std; using ll=long long; #define F first #define S second #define sz(x) int(x.size()) const ll INF=1e18+5; int n; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; vector<int> a(n+1); for(int i=1; i<=n; i++) { cin >> a[i]; } vector<ll> f(n+1); for(int k=1; k<=n; k++) { cin >> f[k]; } for(int i=0; i<n-1; i++) { int x, y; cin >> x >> y; } vector<ll> suff(n+1); suff[n]=f[n]; for(int i=n-1; i>=1; i--) { suff[i]=min(suff[i+1], f[i]); } vector<ll> dp(n+1, INF); dp[0]=0; dp[1]=suff[a[1]+1]; vector<int> poc(n+1); poc[1]=1; for(int i=2; i<=n; i++) { if(a[i-1]+1==a[i]) { poc[i]=poc[i-1]; } else { poc[i]=i; } } for(int i=1; i<=n; i++) { dp[i]=dp[poc[i]-1]+suff[a[i]+1]; } int mora=-1; vector<pair<int, int>> koji(n+1, make_pair(-1, -1)); for(int i=2; i<=n; i++) { if(a[i]==0) { if(mora==a[i-1]+1) { koji[i]=koji[i-1]; } else { mora=a[i-1]+1; koji[i]=make_pair(i-1, mora); } } else { if(a[i-1]+1!=a[i]) { mora=-1; } else if(mora!=-1) { if(mora>a[i]) { koji[i]=koji[i-1]; } } } } for(int i=1; i<=n; i++) { if(koji[i].S!=-1) { dp[i]=min(dp[i], dp[koji[i].F-1]+f[koji[i].S]); } } cout << dp[n] << '\n'; return 0; }
#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...