Submission #1130833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130833		Champ_Naman	Fireworks (APIO16_fireworks)	C++20	19 / 100	10 ms	1096 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'

const int N = 301;
vector<pair<int,int>> g[N];
int dp[N][N];

void dfs(int v){
   for(auto [ch, w] : g[v]){
      dfs(ch);

      for(int i=0; i<=300; i++){
         int mn = 1e18;
         for(int j=0; j<=i; j++){
            int reqw = i - j;
            mn = min(mn, dp[ch][j] + abs(w - reqw));
         }

         if(mn == 1e18){
            dp[v][i] = 1e18;
            break;
         }
         dp[v][i] += mn;
      }
   }

   if(g[v].size() == 0){
      for(int i=1; i<=300; i++) dp[v][i] = 1e18;
      dp[v][0] = 0;
   }
}

inline void solve(){
   int n, m;
   cin>>n>>m;
   for(int i=2; i<=n+m; i++){
      int p, c;
      cin>>p>>c;
      g[p].push_back({i, c});
   }

   dfs(1);
   int ans = 1e18;
   for(int i=0; i<=300; i++) ans = min(ans, dp[1][i]);
   cout<<ans;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45