#include "job.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
bool comp(const array<ll,2>& a, const array<ll,2>& b) {
if(a[1]*b[0]==b[1]*a[0]) {
return a[1]<b[1];
}
return a[1]*b[0] < b[1]*a[0];
}
// abcde
struct DS {
vector<array<ll,2>> ts;
void root(int u,int d) { // O(1)
ts.push_back({ts.empty()?u:ts.back()[0]+u,d});
}
void merge(DS& o) {
vector<array<ll,2>> together;
auto it = ts.rbegin(), it2 = o.ts.rbegin();
ll u = ts.back()[0];
ll ou = o.ts.back()[0];
while(it!=ts.rend() or it2!=o.ts.rend()) {
if(it2==o.ts.rend() or (it!=ts.rend() and comp(*it,*it2))) {
(*it)[0]+=ou;
together.push_back(*it);
++it;
if(it==ts.rend()) u=0;
else u = (*it)[0];
} else {
(*it2)[0]+=u;
together.push_back(*it2);
++it2;
if(it2==o.ts.rend()) ou=0;
else ou = (*it2)[0];
}
}
swap(ts,together);
reverse(all(ts));
}
ll ans() {
ll res=0;
ll pd=0;
for(auto& [u,d] : ts) {
res+=u*d;
}
return res;
}
};
long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
// merge chains?
int n = p.size();
// just loop backwards, and maintain those?
vector<DS> dp(n);
for(int i=n-1;i>=0;--i) {
// add root
dp[i].root(u[i],d[i]);
if(p[i]!=-1) {
if(dp[p[i]].ts.empty()) swap(dp[i],dp[p[i]]);
else dp[p[i]].merge(dp[i]);
}
}
return dp[0].ans() ;
}
Compilation message
job.cpp: In member function 'll DS::ans()':
job.cpp:54:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | for(auto& [u,d] : ts) {
| ^
job.cpp:53:6: warning: unused variable 'pd' [-Wunused-variable]
53 | ll pd=0;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
18 ms |
3696 KB |
Output is correct |
6 |
Correct |
28 ms |
7088 KB |
Output is correct |
7 |
Correct |
40 ms |
11508 KB |
Output is correct |
8 |
Correct |
54 ms |
13872 KB |
Output is correct |
9 |
Correct |
52 ms |
13880 KB |
Output is correct |
10 |
Correct |
62 ms |
13996 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
53 ms |
13888 KB |
Output is correct |
13 |
Correct |
54 ms |
13884 KB |
Output is correct |
14 |
Correct |
51 ms |
13904 KB |
Output is correct |
15 |
Correct |
53 ms |
13872 KB |
Output is correct |
16 |
Correct |
52 ms |
13868 KB |
Output is correct |
17 |
Correct |
54 ms |
13868 KB |
Output is correct |
18 |
Correct |
56 ms |
13872 KB |
Output is correct |
19 |
Correct |
52 ms |
13892 KB |
Output is correct |
20 |
Correct |
51 ms |
13892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
18 ms |
3696 KB |
Output is correct |
6 |
Correct |
28 ms |
7088 KB |
Output is correct |
7 |
Correct |
40 ms |
11508 KB |
Output is correct |
8 |
Correct |
54 ms |
13872 KB |
Output is correct |
9 |
Correct |
52 ms |
13880 KB |
Output is correct |
10 |
Correct |
62 ms |
13996 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
53 ms |
13888 KB |
Output is correct |
13 |
Correct |
54 ms |
13884 KB |
Output is correct |
14 |
Correct |
51 ms |
13904 KB |
Output is correct |
15 |
Correct |
53 ms |
13872 KB |
Output is correct |
16 |
Correct |
52 ms |
13868 KB |
Output is correct |
17 |
Correct |
54 ms |
13868 KB |
Output is correct |
18 |
Correct |
56 ms |
13872 KB |
Output is correct |
19 |
Correct |
52 ms |
13892 KB |
Output is correct |
20 |
Correct |
51 ms |
13892 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |