Submission #23531

#	Time	Username	Problem	Language	Result	Execution time	Memory
23531		Nirjhor	Fireworks (APIO16_fireworks)	C++14	0 / 100	2000 ms	2388 KiB

fireworks

#include <bits/stdc++.h> 

using namespace std;

typedef pair <int, int> edge;

const int N = 305;

vector <edge> g[N];
int n, nn, m, dp[N][N];

int call (int u, int cost, int fr) {
  // cout << u << " " << cost << endl;
  if (u > nn) return cost == 0 ? 0 : 1000 * 1000;
  if (dp[u][cost] != -1) return dp[u][cost];
  dp[u][cost] = 0;
  for (edge e : g[u]) {
    int v = e.first;
    if (v == fr) continue;
    int w = e.second;
    int cur = 1000 * 1000;
    for (int j = 0; j <= max(w, cost); ++j) {
      int ncost = cost - w + j;
      if (ncost >= 0) {
        cur = min(cur, j + call(v, ncost, u));
        // cout << cur << endl;
      }
      ncost = cost - w - j;
      if (ncost >= 0) {
        cur = min(cur, j + call(v, ncost, u));
        // cout << cur << endl;
      }
    } 
    // cout << "wyt " << " " << w << endl;
    // cout << "fr " << u << "  to   " << v << "  ---> " << cur << endl;
    dp[u][cost] += cur;
  }
  return dp[u][cost];
}

int main (int argc, char const *argv[]) {
  scanf("%d %d", &n, &m);
  nn = n; n += m;
  for (int i = 2; i <= n; ++i) {
    int p, c;
    scanf("%d %d", &p, &c);
    g[i].push_back(edge(p, c));
    g[p].push_back(edge(i, c));
  }
  memset(dp, -1, sizeof dp);
  int ans = 1000 * 1000 * 1000;
  // cout << call(3, 3, 2) << endl; 
  for (int i = 0; i < N; ++i) {
    ans = min(ans, call(1, i, -1));
  }
  // for (int i = 1; i <= n; ++i) {
  //   for (int j = 0; j <= 5; ++j) {
  //     cout << "(" << i << ", " << j << ") ---> " << dp[i][j] << endl;
  //   }
  // }
  printf("%d\n", ans);
  return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main(int, const char**)':
fireworks.cpp:42:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
                         ^
fireworks.cpp:46:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &p, &c);
                           ^

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