Submission #153794

#	Time	Username	Problem	Language	Result	Execution time	Memory
153794		arnold518	Fireworks (APIO16_fireworks)	C++14	19 / 100	28 ms	7928 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, M;
vector<pii> adj[MAXN+10];
int dp[MAXN+10][400], ans=987654321;

void dfs(int now)
{
    int i, j;

    if(now>N)
    {
        dp[now][0]=0;
        for(i=1; i<=300; i++) dp[now][i]=987654321;
        return;
    }

    for(auto nxt : adj[now]) dfs(nxt.first);

    for(i=0; i<=300; i++)
    {
        dp[now][i]=0;
        for(auto nxt : adj[now])
        {
            int t=987654321;
            for(j=0; j<=i; j++) t=min(t, dp[nxt.first][j]+abs(i-j-nxt.second));
            dp[now][i]+=t;
        }
    }
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &M);
    for(i=2; i<=N+M; i++)
    {
        int p, c;
        scanf("%d%d", &p, &c);
        adj[p].push_back({i, c});
    }

    dfs(1);
    ans=987654321;
    for(i=0; i<=300; i++) ans=min(ans, dp[1][i]);
    printf("%d", ans);
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:41:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
fireworks.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:47:14: 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: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45