Submission #47323

#	Time	Username	Problem	Language	Result	Execution time	Memory
47323		Talant	Fireworks (APIO16_fireworks)	C++17	19 / 100	32 ms	6164 KiB

fireworks

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)2e5 + 7;

int n,m;
int x,w;
int dp[302][302];
int ans = inf;

vector <pair<int,int> > g[N];

void dfs (int v) {
      for (auto to : g[v]) {
            dfs(to.fr);
            int u = to.fr;
            int w = to.sc;
            for (int i = 0; i <= 300; i ++) {
                  int mn = inf;
                  for (int j = 0; j <= i; j ++) {
                        mn = min(mn,dp[u][j] + abs(i - j - w));
                  }

                  dp[v][i] += mn;
            }
      }
}
main () {
      cin >> n >> m;

      for (int i = 2; i <= n + m; i ++) {
            cin >> x >> w;
            g[x].pb(mk(i,w));
      }
      for (int i = n + 1; i <= n + m; i ++)
            for (int j = 1; j <= 300; j ++)
                  dp[i][j] = inf;

      dfs(1);

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

      cout << ans << endl;
}

Compilation message (stderr)

fireworks.cpp:38:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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