Submission #409647

#	Time	Username	Problem	Language	Result	Execution time	Memory
409647		juggernaut	Fireworks (APIO16_fireworks)	C++17	26 / 100	29 ms	15272 KiB

fireworks

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
typedef long long ll;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef IOI2021SG
    #define printl(args...)printf(args)
#else
    #define printl(args...)((void)0)
#endif
vector<pair<int,int>>g[300005];
int dp[305][305],n,m;
void dfs(int v){
    if(v>n){
        dp[v][0]=0;
        for(int i=1;i<=300;i++)dp[v][i]=1e9;
        return;
    }
    for(auto &[to,w]:g[v]){
        dfs(to);
        for(int i=0;i<=300;i++){
            int mn=1e7;
            for(int j=0;j<=i;j++)umin(mn,dp[to][j]+abs(i-j-w));
            dp[v][i]+=mn;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    if(n==1){
        vector<int>v;
        for(int i=2;i<=n+m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            v.push_back(y);
        }
        ll ans=9e18;
        for(int x:v){
            ll cnt=0;
            for(int y:v)cnt+=abs(x-y);
            umin(ans,cnt);
        }
        printf("%lld",ans);
        exit(0);
    }
    for(int i=2;i<=n+m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].emplace_back(i,y);
    }
    dfs(1);
    int ans=2e9;
    for(int i=0;i<=300;i++)umin(ans,dp[1][i]);
    printf("%d",ans);
}

Compilation message (stderr)

fireworks.cpp: In function 'void usaco(std::string)':
fireworks.cpp:5:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:5:66: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
fireworks.cpp:43:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |             scanf("%d%d",&x,&y);
      |             ~~~~~^~~~~~~~~~~~~~
fireworks.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

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