oj.uz

Submission #706836

# Submission time Handle Problem Language Result Execution time Memory
706836 2023-03-07T21:32:58 Z AdamGS Job Scheduling (IOI19_job) C++17
5 / 100
 90 ms 48916 KB 
#include "job.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
vector<int>V[LIM];
ll dp[LIM], sumu[LIM], sumczas[LIM], n;
bool srt(pair<ll,ll>a, pair<ll,ll>b) {
    return a.st*b.nd-a.nd*b.st<0;
}
void DFS(int x) {
    ll a=sumczas[x];
    vector<pair<ll,ll>>P;
    for(auto i : V[x]) {
        DFS(i);
        P.pb({sumczas[i], sumu[i]});
        sumu[x]+=sumu[i];
        sumczas[x]+=sumczas[i];
        dp[x]+=dp[i];
    }
    sort(P.begin(), P.end(), srt);
    ll akt=0;
    for(int i=P.size()-1; i>=0; --i) {
        dp[x]+=P[i].nd*akt;
        akt+=P[i].st;
    }
    dp[x]+=a*sumu[x];
}
ll scheduling_cost(vector<int>P, vector<int>U, vector<int>D) {
    n=P.size();
    rep(i, n-1) V[P[i+1]].pb(i+1);
    rep(i, n) {
        sumu[i]=U[i];
        sumczas[i]=D[i];
    }
    DFS(0);
    return dp[0];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5184 KB Output is correct
5 Correct 30 ms 15896 KB Output is correct
6 Correct 42 ms 26828 KB Output is correct
7 Correct 59 ms 37844 KB Output is correct
8 Correct 81 ms 48876 KB Output is correct
9 Correct 82 ms 48824 KB Output is correct
10 Correct 79 ms 48812 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 79 ms 48804 KB Output is correct
13 Correct 81 ms 48796 KB Output is correct
14 Correct 90 ms 48764 KB Output is correct
15 Correct 87 ms 48800 KB Output is correct
16 Correct 84 ms 48820 KB Output is correct
17 Correct 82 ms 48716 KB Output is correct
18 Correct 81 ms 48824 KB Output is correct
19 Correct 87 ms 48916 KB Output is correct
20 Correct 86 ms 48716 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5184 KB Output is correct
5 Correct 30 ms 15896 KB Output is correct
6 Correct 42 ms 26828 KB Output is correct
7 Correct 59 ms 37844 KB Output is correct
8 Correct 81 ms 48876 KB Output is correct
9 Correct 82 ms 48824 KB Output is correct
10 Correct 79 ms 48812 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 79 ms 48804 KB Output is correct
13 Correct 81 ms 48796 KB Output is correct
14 Correct 90 ms 48764 KB Output is correct
15 Correct 87 ms 48800 KB Output is correct
16 Correct 84 ms 48820 KB Output is correct
17 Correct 82 ms 48716 KB Output is correct
18 Correct 81 ms 48824 KB Output is correct
19 Correct 87 ms 48916 KB Output is correct
20 Correct 86 ms 48716 KB Output is correct
21 Incorrect 3 ms 4948 KB Output isn't correct
22 Halted 0 ms 0 KB -