Submission #544557

#TimeUsernameProblemLanguageResultExecution timeMemory
544557leakedWorst Reporter 4 (JOI21_worst_reporter4)C++14
14 / 100
219 ms196872 KiB
#include <bits/stdc++.h> #define f first #define s second #define m_p make_pair #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define vec vector #define pb push_back #define sz(x) (int)(x).size() #define pw(x) (1LL<<(x)) #define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef long double ld; template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);} template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);} const int N=5e3+1; const ll inf=1e18; vec<int> g[N]; ll dp[N][N]; int c[N],a[N],h[N]; void dfs(int v){ // for(int i=0;i<N;i++){ // dp[v][i]=(h[v]==i?0:c[v]); // } // cout<<"DFS "<<v<<endl; for(auto &z : g[v]){ dfs(z); for(int j=0;j<N;j++) dp[v][j]+=dp[z][j]; // for(int j=1;j<N;j++){ // if(umin(dp[v][j],dp[v][j-1])) // cerr<<"V "<<v<<' '<<j<<endl; // } } for(int j=N-1;j>=0;j--){ dp[v][j]=min(dp[v][j]+(j==h[v]?0:c[v]),(j+1<N?dp[v][j+1]:inf)); } // for(int j=0;j<N;j++){ // cerr<<"DE "<<dp[v][j]<<' '<<v<<' '<<j<<endl; // } } signed main(){ fast_resp; int n; cin>>n; vec<int>kek; for(int i=0;i<n;i++){ cin>>a[i]>>h[i]>>c[i];--a[i]; if(a[i]!=i) g[a[i]].pb(i); kek.pb(h[i]); } sort(all(kek));kek.erase(unique(all(kek)),kek.end()); for(int i=0;i<n;i++) h[i]=lower_bound(all(kek),h[i])-kek.begin(); dfs(0); cout<<dp[0][0]; return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...