Submission #69314

#TimeUsernameProblemLanguageResultExecution timeMemory
69314FedericoSFireworks (APIO16_fireworks)C++14
0 / 100
6 ms484 KiB
#pragma GCC optimize("Ofast") #include <iostream> #include <algorithm> #include <vector> using namespace std; typedef long long int ll; typedef pair<ll,ll> pll; ll x,y; ll INF=1e18; ll N,M,K=600; ll DP[305][500]; vector<pll> grafo[305]; ll ans; void DFS(ll k, ll p){ if(k>N){ for(int i=1;i<K;i++) DP[k][i]=INF; return; } for(pll f:grafo[k]) if(f.first!=p) DFS(f.first,k); for(int i=0;i<K;i++) for(pll f:grafo[k]) if(f.first!=p){ ll res=INF; for(int j=0;j<=i;j++) res=min(res,DP[f.first][j]+abs(f.second-(i-j))); DP[k][i]+=res; } } int main(){ cin>>N>>M; for(int i=2;i<=N+M;i++){ cin>>x>>y; grafo[i].push_back({x,y}); grafo[x].push_back({i,y}); } DFS(1,0); ans=INF; for(int i=0;i<K;i++) ans=min(ans,DP[1][i]); cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...