oj.uz

Submission #706826

# Submission time Handle Problem Language Result Execution time Memory
706826 2023-03-07T21:12:03 Z AdamGS Job Scheduling (IOI19_job) C++17
17 / 100
 109 ms 52084 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(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 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 5144 KB Output is correct
5 Correct 23 ms 16724 KB Output is correct
6 Correct 43 ms 28404 KB Output is correct
7 Correct 64 ms 40220 KB Output is correct
8 Correct 86 ms 51988 KB Output is correct
9 Correct 83 ms 51984 KB Output is correct
10 Correct 85 ms 51988 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 109 ms 51984 KB Output is correct
13 Correct 89 ms 52084 KB Output is correct
14 Correct 81 ms 51916 KB Output is correct
15 Correct 85 ms 51956 KB Output is correct
16 Correct 82 ms 52016 KB Output is correct
17 Correct 89 ms 52012 KB Output is correct
18 Correct 96 ms 51996 KB Output is correct
19 Correct 80 ms 51888 KB Output is correct
20 Correct 89 ms 51916 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Runtime error 77 ms 38916 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 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 6 ms 5956 KB Output is correct
6 Correct 81 ms 21140 KB Output is correct
7 Correct 77 ms 21148 KB Output is correct
8 Correct 103 ms 21160 KB Output is correct
9 Correct 84 ms 21204 KB Output is correct
10 Correct 3 ms 5008 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 6 ms 5844 KB Output is correct
13 Correct 6 ms 5972 KB Output is correct
14 Correct 78 ms 21128 KB Output is correct
15 Correct 80 ms 21232 KB Output is correct
16 Correct 88 ms 21180 KB Output is correct
17 Correct 89 ms 21128 KB Output is correct
18 Correct 77 ms 21200 KB Output is correct
19 Correct 80 ms 21180 KB Output is correct
20 Correct 82 ms 21116 KB Output is correct
21 Correct 82 ms 21124 KB Output is correct
22 Correct 80 ms 21164 KB Output is correct
23 Correct 78 ms 21132 KB Output is correct
24 Correct 84 ms 21148 KB Output is correct

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 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 5144 KB Output is correct
5 Correct 23 ms 16724 KB Output is correct
6 Correct 43 ms 28404 KB Output is correct
7 Correct 64 ms 40220 KB Output is correct
8 Correct 86 ms 51988 KB Output is correct
9 Correct 83 ms 51984 KB Output is correct
10 Correct 85 ms 51988 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 109 ms 51984 KB Output is correct
13 Correct 89 ms 52084 KB Output is correct
14 Correct 81 ms 51916 KB Output is correct
15 Correct 85 ms 51956 KB Output is correct
16 Correct 82 ms 52016 KB Output is correct
17 Correct 89 ms 52012 KB Output is correct
18 Correct 96 ms 51996 KB Output is correct
19 Correct 80 ms 51888 KB Output is correct
20 Correct 89 ms 51916 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 5004 KB Output is correct
23 Correct 3 ms 5000 KB Output is correct
24 Runtime error 77 ms 38916 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -