Submission #493945

#	Time	Username	Problem	Language	Result	Execution time	Memory
493945		trumchepcode	Fireworks (APIO16_fireworks)	C++14	26 / 100	91 ms	12264 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
const int N=5001;
const long long inf = 1e9;
int n,m;
vector<pair<int,long long>> edge[N];
long long dp[N][302];
long long sol(int u, int left)
{
    if (edge[u].size() == 0)
    {
        return 0;
    }
    long long& ret = dp[u][left];
    if (ret != -1)
    {
        return ret;
    }
    ret = 0;
    for (pair<int, long long> p : edge[u])
    {
        long long sub = inf;
        int v = p.first;
        long long w = p.second;
        if (edge[v].size() == 0)
        {
            sub = abs(w - left);
            ret += sub;
            continue;
        }
        for (int j = 0; j <= left; j++)
        {
            sub = min(sub, abs(w - j) + sol(v, left - j));
        }
        ret += sub;
    }
    return ret;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   // freopen("dut03phoa.inp","r",stdin);
  //  freopen("dut03phoa.out","w",stdout);
    cin >> n >> m;
    if (n == 1)
    {
        vector<long long> v;
        for (int i = 1; i < n + m; i++)
        {
            int p;
            long long c;
            cin >> p >> c;
            v.emplace_back(c);
        }
        sort(v.begin(), v.end());
        long long trungvi = v[v.size() / 2];
        long long ans = 0;
        for (int i = 0; i <  v.size(); i++)
        {
            ans += abs(trungvi - v[i]);
        }
        cout << ans;
    }
    else
    {
        long long ans = 0;
        for (int i = 1; i < n + m; i++)
        {
            int p;
            long long c;
            cin >> p >> c;
            edge[p - 1].emplace_back(i, c);
            ans += c;
        }
        memset(dp, -1, sizeof dp);
        for (int i = 0; i <= 300; i++)
        {
            ans = min(ans, sol(0, i));
        }
        cout << ans;

    }

}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int i = 0; i <  v.size(); i++)
      |                         ~~^~~~~~~~~~~

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