oj.uz

Submission #952047

# Submission time Handle Problem Language Result Execution time Memory
952047 2024-03-23T04:32:04 Z GrindMachine Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 283 ms 197460 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/88748?#comment-774017 (thread)
got the key idea, but didnt know how to implement in a clean way

implementation idea:
represent the subtree cost @u as a staircase function using a map
can be merged efficiently using small to large

*/

const int MOD = 1e9 + 7;
const int N = 5e3 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<ll> adj[N];
vector<pll> a(N);
ll dp[N][N];
ll n;

void dfs(ll u){
    trav(v,adj[u]){
        dfs(v);
    }

    auto [h,c] = a[u];

    rev(j,n,1){
        dp[u][j] = c;
        if(j == h) dp[u][j] = 0;

        trav(v,adj[u]){
            dp[u][j] += dp[v][j];
        }

        amin(dp[u][j],dp[u][j+1]);
    }
}

void solve(int test_case)
{
    cin >> n;
    rep1(i,n){
        ll p,h,c; cin >> p >> h >> c;
        if(p != i){
            adj[p].pb(i);
        }
        a[i] = {h,c};
    }

    vector<ll> b;
    rep1(i,n) b.pb(a[i].ff);

    sort(all(b));
    rep1(i,n) a[i].ff = lower_bound(all(b),a[i].ff)-b.begin()+1;

    memset(dp,0x3f,sizeof dp);
    dfs(1);

    ll ans = inf2;
    rep1(j,n) amin(ans,dp[1][j]);
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 196624 KB Output is correct
2 Correct 26 ms 196644 KB Output is correct
3 Correct 26 ms 196688 KB Output is correct
4 Correct 25 ms 196700 KB Output is correct
5 Correct 92 ms 196916 KB Output is correct
6 Correct 101 ms 196944 KB Output is correct
7 Correct 108 ms 197032 KB Output is correct
8 Correct 104 ms 197040 KB Output is correct
9 Correct 106 ms 197044 KB Output is correct
10 Correct 108 ms 197024 KB Output is correct
11 Correct 103 ms 196956 KB Output is correct
12 Correct 69 ms 197200 KB Output is correct
13 Correct 72 ms 197328 KB Output is correct
14 Correct 69 ms 197460 KB Output is correct
15 Correct 82 ms 197456 KB Output is correct
16 Correct 79 ms 196884 KB Output is correct
17 Correct 87 ms 196956 KB Output is correct
18 Correct 105 ms 197012 KB Output is correct
19 Correct 99 ms 197140 KB Output is correct
20 Correct 99 ms 196904 KB Output is correct
21 Correct 101 ms 196944 KB Output is correct
22 Correct 278 ms 197156 KB Output is correct
23 Correct 283 ms 196948 KB Output is correct
24 Correct 156 ms 197160 KB Output is correct
25 Correct 163 ms 197160 KB Output is correct
26 Correct 66 ms 197212 KB Output is correct
27 Correct 87 ms 196948 KB Output is correct
28 Correct 75 ms 196948 KB Output is correct
29 Correct 70 ms 197232 KB Output is correct
30 Correct 67 ms 197052 KB Output is correct
31 Correct 68 ms 197200 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 196624 KB Output is correct
2 Correct 26 ms 196644 KB Output is correct
3 Correct 26 ms 196688 KB Output is correct
4 Correct 25 ms 196700 KB Output is correct
5 Correct 92 ms 196916 KB Output is correct
6 Correct 101 ms 196944 KB Output is correct
7 Correct 108 ms 197032 KB Output is correct
8 Correct 104 ms 197040 KB Output is correct
9 Correct 106 ms 197044 KB Output is correct
10 Correct 108 ms 197024 KB Output is correct
11 Correct 103 ms 196956 KB Output is correct
12 Correct 69 ms 197200 KB Output is correct
13 Correct 72 ms 197328 KB Output is correct
14 Correct 69 ms 197460 KB Output is correct
15 Correct 82 ms 197456 KB Output is correct
16 Correct 79 ms 196884 KB Output is correct
17 Correct 87 ms 196956 KB Output is correct
18 Correct 105 ms 197012 KB Output is correct
19 Correct 99 ms 197140 KB Output is correct
20 Correct 99 ms 196904 KB Output is correct
21 Correct 101 ms 196944 KB Output is correct
22 Correct 278 ms 197156 KB Output is correct
23 Correct 283 ms 196948 KB Output is correct
24 Correct 156 ms 197160 KB Output is correct
25 Correct 163 ms 197160 KB Output is correct
26 Correct 66 ms 197212 KB Output is correct
27 Correct 87 ms 196948 KB Output is correct
28 Correct 75 ms 196948 KB Output is correct
29 Correct 70 ms 197232 KB Output is correct
30 Correct 67 ms 197052 KB Output is correct
31 Correct 68 ms 197200 KB Output is correct
32 Correct 109 ms 196832 KB Output is correct
33 Runtime error 6 ms 1372 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 196624 KB Output is correct
2 Correct 26 ms 196644 KB Output is correct
3 Correct 26 ms 196688 KB Output is correct
4 Correct 25 ms 196700 KB Output is correct
5 Correct 92 ms 196916 KB Output is correct
6 Correct 101 ms 196944 KB Output is correct
7 Correct 108 ms 197032 KB Output is correct
8 Correct 104 ms 197040 KB Output is correct
9 Correct 106 ms 197044 KB Output is correct
10 Correct 108 ms 197024 KB Output is correct
11 Correct 103 ms 196956 KB Output is correct
12 Correct 69 ms 197200 KB Output is correct
13 Correct 72 ms 197328 KB Output is correct
14 Correct 69 ms 197460 KB Output is correct
15 Correct 82 ms 197456 KB Output is correct
16 Correct 79 ms 196884 KB Output is correct
17 Correct 87 ms 196956 KB Output is correct
18 Correct 105 ms 197012 KB Output is correct
19 Correct 99 ms 197140 KB Output is correct
20 Correct 99 ms 196904 KB Output is correct
21 Correct 101 ms 196944 KB Output is correct
22 Correct 278 ms 197156 KB Output is correct
23 Correct 283 ms 196948 KB Output is correct
24 Correct 156 ms 197160 KB Output is correct
25 Correct 163 ms 197160 KB Output is correct
26 Correct 66 ms 197212 KB Output is correct
27 Correct 87 ms 196948 KB Output is correct
28 Correct 75 ms 196948 KB Output is correct
29 Correct 70 ms 197232 KB Output is correct
30 Correct 67 ms 197052 KB Output is correct
31 Correct 68 ms 197200 KB Output is correct
32 Correct 109 ms 196832 KB Output is correct
33 Runtime error 6 ms 1372 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -