oj.uz

Submission #403973

# Submission time Handle Problem Language Result Execution time Memory
403973 2021-05-13T16:06:28 Z teehandsome Fireworks (APIO16_fireworks) C++11
19 / 100
 102 ms 736 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxn=310;
vector<pii> adj[mxn];
int dp[mxn][mxn];
int n,m;

int dfs(int u,int sum) {
    if(dp[u][sum]!=-1) return dp[u][sum];
    if(adj[u].empty()) return sum;
    int res=0;
    for(auto vw:adj[u]) {
        int temp=INF;
        int v=vw.first,w=vw.second;
        for(int i=0;i<=sum;i++) {
            temp=min(temp,abs(i-w)+dfs(v,sum-i));
        }
        res+=temp;
    }

    return dp[u][sum]=res;
}

int main () {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    memset(dp,-1,sizeof(dp));
    for(int i=2;i<=n+m;i++) {
        int u,w; cin>>u>>w;
        adj[u].push_back({i,w});
    }
    int ans=INF;
    for(int i=0;i<=300;i++) {
        ans=min(ans,dfs(1,i));
//        debug(i,dp[1][i]);
    }
    cout<<ans<<endl;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 10 ms 588 KB Output is correct
3 Correct 16 ms 588 KB Output is correct
4 Correct 9 ms 716 KB Output is correct
5 Correct 70 ms 684 KB Output is correct
6 Correct 36 ms 684 KB Output is correct
7 Correct 47 ms 684 KB Output is correct
8 Correct 42 ms 588 KB Output is correct
9 Correct 43 ms 588 KB Output is correct
10 Correct 47 ms 684 KB Output is correct
11 Correct 72 ms 588 KB Output is correct
12 Correct 59 ms 684 KB Output is correct
13 Correct 61 ms 588 KB Output is correct
14 Correct 24 ms 736 KB Output is correct
15 Correct 68 ms 684 KB Output is correct
16 Correct 102 ms 684 KB Output is correct
17 Correct 68 ms 684 KB Output is correct
18 Correct 69 ms 588 KB Output is correct
19 Correct 74 ms 588 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -