oj.uz

Submission #706827

# Submission time Handle Problem Language Result Execution time Memory
706827 2023-03-07T21:15:20 Z AdamGS Job Scheduling (IOI19_job) C++17
17 / 100
 96 ms 56968 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=5e5+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(all(P), srt);
    ll akt=0;
    rep(i, P.size()) {
        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];
}

Compilation message

job.cpp: In function 'void DFS(int)':
job.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
job.cpp:28:5: note: in expansion of macro 'rep'
   28 |     rep(i, P.size()) {
      |     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12048 KB Output is correct
3 Correct 7 ms 12064 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 27 ms 23704 KB Output is correct
6 Correct 46 ms 34984 KB Output is correct
7 Correct 65 ms 45936 KB Output is correct
8 Correct 89 ms 56892 KB Output is correct
9 Correct 83 ms 56888 KB Output is correct
10 Correct 87 ms 56968 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 83 ms 56844 KB Output is correct
13 Correct 92 ms 56920 KB Output is correct
14 Correct 82 ms 56908 KB Output is correct
15 Correct 86 ms 56868 KB Output is correct
16 Correct 90 ms 56868 KB Output is correct
17 Correct 82 ms 56808 KB Output is correct
18 Correct 84 ms 56860 KB Output is correct
19 Correct 86 ms 56832 KB Output is correct
20 Correct 83 ms 56840 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12052 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12052 KB Output is correct
4 Runtime error 81 ms 52512 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11960 KB Output is correct
3 Correct 6 ms 12048 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 10 ms 13024 KB Output is correct
6 Correct 84 ms 26872 KB Output is correct
7 Correct 96 ms 26928 KB Output is correct
8 Correct 86 ms 26884 KB Output is correct
9 Correct 84 ms 26944 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 8 ms 12116 KB Output is correct
12 Correct 10 ms 12884 KB Output is correct
13 Correct 10 ms 13052 KB Output is correct
14 Correct 83 ms 26960 KB Output is correct
15 Correct 84 ms 26868 KB Output is correct
16 Correct 83 ms 26964 KB Output is correct
17 Correct 83 ms 26976 KB Output is correct
18 Correct 80 ms 26928 KB Output is correct
19 Correct 86 ms 26944 KB Output is correct
20 Correct 84 ms 26872 KB Output is correct
21 Correct 83 ms 26932 KB Output is correct
22 Correct 82 ms 26864 KB Output is correct
23 Correct 84 ms 26932 KB Output is correct
24 Correct 85 ms 26936 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12052 KB Output is correct
2 Incorrect 7 ms 12048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12048 KB Output is correct
3 Correct 7 ms 12064 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 27 ms 23704 KB Output is correct
6 Correct 46 ms 34984 KB Output is correct
7 Correct 65 ms 45936 KB Output is correct
8 Correct 89 ms 56892 KB Output is correct
9 Correct 83 ms 56888 KB Output is correct
10 Correct 87 ms 56968 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 83 ms 56844 KB Output is correct
13 Correct 92 ms 56920 KB Output is correct
14 Correct 82 ms 56908 KB Output is correct
15 Correct 86 ms 56868 KB Output is correct
16 Correct 90 ms 56868 KB Output is correct
17 Correct 82 ms 56808 KB Output is correct
18 Correct 84 ms 56860 KB Output is correct
19 Correct 86 ms 56832 KB Output is correct
20 Correct 83 ms 56840 KB Output is correct
21 Correct 7 ms 12052 KB Output is correct
22 Correct 6 ms 11988 KB Output is correct
23 Correct 6 ms 12052 KB Output is correct
24 Runtime error 81 ms 52512 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -