Submission #21843

#	Time	Username	Problem	Language	Result	Execution time	Memory
21843		mohammad_kilani	Fireworks (APIO16_fireworks)	C++14	26 / 100	83 ms	2396 KiB

fireworks

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

int n,m;
vector<vector<pair<int,int> > > g;

int dp[310][310];

int calc(int i,int j){
    if(dp[i][j] == -1){
        int si = g[i].size();
        dp[i][j] = 0 ;
        for(int k=0;k<si;k++){
            int node = g[i][k].first ;
            int cost = 1e9;
            if(node > n){
                int dis = j - g[i][k].second;
                if(dis < 0)
                dis*=-1;
                cost = dis ;
            }
            else {
            for(int l=0;l<=j;l++){
                int dis = (j - l) - g[i][k].second;
                if(dis < 0)
                dis*=-1;
                cost = min(cost,dis+calc(node,l));
            }
        }
            dp[i][j] +=cost;
        }

    }
    return dp[i][j];

}

int main(){
//freopen("in.in","r",stdin);
memset(dp,-1,sizeof(dp));
    scanf("%d%d",&n,&m);
    g.resize(n+m+10);
    for(int i=2;i<=n+m;i++){
            int p,c;
            scanf("%d%d",&p,&c);
            g[p].push_back(make_pair(i,c));
    }
    if(n == 1){
        int si = g[1].size();
        long long ans = 1e16;
        for(int i=0;i<si;i++){
                int num = g[1][i].second;
                long long all = 0 ;
            for(int j=0;j<si;j++){
                int cur = g[1][j].second - num;
                if(cur < 0)
                    cur*=-1;
                all+=(long long)cur;
            }
            ans = min(ans,all);
        }
        cout << ans << endl;
        return 0;
    }
    int ans = 1e9;
    for(int i =0;i<305;i++){
        ans = min(ans,calc(1,i));
    }
    cout << ans << endl;
   return 0;
}

Compilation message (stderr)

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

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