oj.uz

Submission #893863

# Submission time Handle Problem Language Result Execution time Memory
893863 2023-12-27T15:01:03 Z danikoynov Worst Reporter 4 (JOI21_worst_reporter4) C++14
14 / 100
 464 ms 398680 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int maxn = 5010;
const ll inf = 1e18;

int n, a[maxn], h[maxn];
ll c[maxn];
vector < int > adj[maxn];
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i] >> h[i] >> c[i];
        if (a[i] != i)
            adj[a[i]].push_back(i);
    }
}

unordered_map < int, int > tag;

void compress()
{
    vector < int > values;
    for (int i = 1; i <= n; i ++)
        values.push_back(h[i]);

    sort(values.begin(), values.end());

    for (int i = 0; i < n; i ++)
        tag[values[i]] = i + 1;

}

ll dp[maxn][maxn], temp[maxn];
int used[maxn];

void dfs(int v)
{
    for (int j = 1; j <= n; j ++)
    {
        dp[v][j] = c[v];
        if (j == tag[h[v]])
            dp[v][j] = 0;
    }

    used[v] = 1;
    for (int u : adj[v])
    {
        dfs(u);

        for (int j = n; j >= 1; j --)
        {
            dp[v][j] += dp[u][j];
        }
    }

    for (int j = n - 1; j > 0; j --)
    {
        dp[v][j] = min(dp[v][j], dp[v][j + 1]);
    }
    /**cout << "state " << v << " " << h[v] << endl;
    for (int j = 1; j <= n; j ++)
        cout << dp[v][j] << " ";
    cout << endl;*/
}
void calculate_states()
{
    ll ans = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (used[i])
            continue;

        dfs(i);
        ll best = inf;
        for (int j = 1; j <= n; j ++)
        {
            best = min(best, dp[i][j]);
        }

        ans += best;
    }

    cout << ans << endl;
}
void solve()
{
    input();
    compress();
    calculate_states();
}

int main()
{
    solve();
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 372 ms 196836 KB Output is correct
6 Correct 370 ms 196692 KB Output is correct
7 Correct 355 ms 196672 KB Output is correct
8 Correct 357 ms 196948 KB Output is correct
9 Correct 389 ms 196956 KB Output is correct
10 Correct 354 ms 196680 KB Output is correct
11 Correct 318 ms 196676 KB Output is correct
12 Correct 368 ms 197220 KB Output is correct
13 Correct 464 ms 197368 KB Output is correct
14 Correct 360 ms 197204 KB Output is correct
15 Correct 366 ms 196984 KB Output is correct
16 Correct 357 ms 196944 KB Output is correct
17 Correct 372 ms 196788 KB Output is correct
18 Correct 299 ms 196692 KB Output is correct
19 Correct 359 ms 197332 KB Output is correct
20 Correct 391 ms 196944 KB Output is correct
21 Correct 354 ms 196868 KB Output is correct
22 Correct 358 ms 196808 KB Output is correct
23 Correct 369 ms 196980 KB Output is correct
24 Correct 361 ms 196944 KB Output is correct
25 Correct 371 ms 197024 KB Output is correct
26 Correct 363 ms 197204 KB Output is correct
27 Correct 363 ms 196968 KB Output is correct
28 Correct 356 ms 197188 KB Output is correct
29 Correct 361 ms 197264 KB Output is correct
30 Correct 358 ms 197020 KB Output is correct
31 Correct 361 ms 197128 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 372 ms 196836 KB Output is correct
6 Correct 370 ms 196692 KB Output is correct
7 Correct 355 ms 196672 KB Output is correct
8 Correct 357 ms 196948 KB Output is correct
9 Correct 389 ms 196956 KB Output is correct
10 Correct 354 ms 196680 KB Output is correct
11 Correct 318 ms 196676 KB Output is correct
12 Correct 368 ms 197220 KB Output is correct
13 Correct 464 ms 197368 KB Output is correct
14 Correct 360 ms 197204 KB Output is correct
15 Correct 366 ms 196984 KB Output is correct
16 Correct 357 ms 196944 KB Output is correct
17 Correct 372 ms 196788 KB Output is correct
18 Correct 299 ms 196692 KB Output is correct
19 Correct 359 ms 197332 KB Output is correct
20 Correct 391 ms 196944 KB Output is correct
21 Correct 354 ms 196868 KB Output is correct
22 Correct 358 ms 196808 KB Output is correct
23 Correct 369 ms 196980 KB Output is correct
24 Correct 361 ms 196944 KB Output is correct
25 Correct 371 ms 197024 KB Output is correct
26 Correct 363 ms 197204 KB Output is correct
27 Correct 363 ms 196968 KB Output is correct
28 Correct 356 ms 197188 KB Output is correct
29 Correct 361 ms 197264 KB Output is correct
30 Correct 358 ms 197020 KB Output is correct
31 Correct 361 ms 197128 KB Output is correct
32 Correct 359 ms 196948 KB Output is correct
33 Runtime error 329 ms 398680 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 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 372 ms 196836 KB Output is correct
6 Correct 370 ms 196692 KB Output is correct
7 Correct 355 ms 196672 KB Output is correct
8 Correct 357 ms 196948 KB Output is correct
9 Correct 389 ms 196956 KB Output is correct
10 Correct 354 ms 196680 KB Output is correct
11 Correct 318 ms 196676 KB Output is correct
12 Correct 368 ms 197220 KB Output is correct
13 Correct 464 ms 197368 KB Output is correct
14 Correct 360 ms 197204 KB Output is correct
15 Correct 366 ms 196984 KB Output is correct
16 Correct 357 ms 196944 KB Output is correct
17 Correct 372 ms 196788 KB Output is correct
18 Correct 299 ms 196692 KB Output is correct
19 Correct 359 ms 197332 KB Output is correct
20 Correct 391 ms 196944 KB Output is correct
21 Correct 354 ms 196868 KB Output is correct
22 Correct 358 ms 196808 KB Output is correct
23 Correct 369 ms 196980 KB Output is correct
24 Correct 361 ms 196944 KB Output is correct
25 Correct 371 ms 197024 KB Output is correct
26 Correct 363 ms 197204 KB Output is correct
27 Correct 363 ms 196968 KB Output is correct
28 Correct 356 ms 197188 KB Output is correct
29 Correct 361 ms 197264 KB Output is correct
30 Correct 358 ms 197020 KB Output is correct
31 Correct 361 ms 197128 KB Output is correct
32 Correct 359 ms 196948 KB Output is correct
33 Runtime error 329 ms 398680 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -