Submission #1015102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015102		vjudge1	Fireworks (APIO16_fireworks)	C++17	26 / 100	14 ms	1176 KiB

fireworks

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 3e2+6;
const ll inf = 1e18;
int n, m;
ll dp[N][N];
vector<pair<int,int> > child[N];

void subtask1()
{
  sort(child[1].begin(), child[1].end());
  ll suf = 0, prf = 0;
  for(auto [w, u] : child[1])
    suf += w;

  ll ans = inf;
  for(int i = 0; i < child[1].size(); i++)
    {
      ll w = child[1][i].first, rem = child[1].size() - i;
      ans = min(ans, i * w - prf + suf - rem * w);
      prf += w;
      suf -= w;
    }
  cout << ans << endl;
}

void dfs(int v)
{
  if(child[v].empty())
    {
      for(int i = 1; i < N; i ++)
	dp[v][i] = inf;
      return;
    }

  for(auto [w, u] : child[v])
    {
      dfs(u);
      for(int i = 0; i < N; i ++)
	{
	  ll ans = N * N;
	  for(int j = 0; j <= i; j++)
	    ans = min(ans, abs(w - j) + dp[u][i  - j]);
	  dp[v][i] += ans;
	  dp[v][i] = min(dp[v][i], inf);
	}
	
    }
  
}

void subtask2()
{
  dfs(1);
  for(int i = 0; i < N; i ++)
    dp[1][0] = min(dp[1][i], dp[1][0]);
  cout << dp[1][0] << endl;
}

int main()
{
  cin >> n >> m;
  for(int i = 2; i <= n + m; i ++)
    {
      int p, w;
      cin >> p >> w;
      child[p].push_back({w, i});
    }

  if(n == 1)
    subtask1();
  else
    subtask2();
  return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void subtask1()':
fireworks.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int i = 0; i < child[1].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~

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