Submission #400680

#	Time	Username	Problem	Language	Result	Execution time	Memory
400680		A_D	Fireworks (APIO16_fireworks)	C++14	19 / 100	21 ms	1016 KiB

fireworks

#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define F first
#define S second
#define du long double
using namespace std;
const int N=301;
int a[N];
int dp[N][N];
vector<ii> g[N];
void dfs(int u)
{
    for(auto x:g[u]){
        dfs(x.F);
        for(int j=0;j<=300;j++){
            int mn=1e18;
            for(int k=0;k<=j;k++){
                mn=min(mn,dp[x.F][k]+abs(j-(x.S+k)));
            }
            dp[u][j]+=mn;
        }
    }
}
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=2;i<=n+m;i++){
        int u,c;
        scanf("%lld",&u);
        scanf("%lld",&c);
        g[u].push_back({i,c});
        if(i>n){
            for(int j=1;j<=300;j++){
                dp[i][j]=1e13;
            }
        }
    }
    dfs(1);
    /*
    cout<<endl;
    for(int i=1;i<=n+m;i++){
        for(int j=1;j<=10;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    */
    int mn=1e18;
    for(int i=0;i<=300;i++)mn=min(mn,dp[1][i]);
    cout<<mn<<endl;
}
main()
{
    int t=1;
//    cin>>t;
    while(t--)solve();
}

Compilation message (stderr)

fireworks.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main()
      |      ^
fireworks.cpp: In function 'void solve()':
fireworks.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |         scanf("%lld",&u);
      |         ~~~~~^~~~~~~~~~~
fireworks.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |         scanf("%lld",&c);
      |         ~~~~~^~~~~~~~~~~

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