oj.uz

Submission #995371

# Submission time Handle Problem Language Result Execution time Memory
995371 2024-06-08T23:40:41 Z PagodePaiva Jobs (BOI24_jobs) C++17
11 / 100
 267 ms 232532 KB 
#include<bits/stdc++.h>
#define int long long
 
using namespace std;
const int N = 300010;
vector <int> g[N];
vector <int> raizes;
int val[N];
int pai[N];
int dp[N];
 
int dfs(int v, int p){
    int con = 0;
    for(auto x : g[v]){
        if(x == p) continue;
        dfs(x, v);
        con++;
    }
    if(con == 0)
        return dp[v] = max(0LL, val[v]);
    int vl = val[v];
    for(auto x : g[v]){
        if(x == p) continue;
        vl += dp[x];
    }
    dp[v] = max(vl, 0LL);
    return dp[v];
}
stack <pair <int, int>> s[N];

int32_t main(){
    int n, c;
    cin >> n >> c;
    if(c >= 1e17){
        for(int i = 1;i <= n;i++){
            int p;
            cin >> val[i] >> p;
            if(p == 0) raizes.push_back(i);
            else g[p].push_back(i);
        }
        int res = 0;
        for(auto x : raizes){
            res += dfs(x, x);
        }
        cout << res << '\n';
        return 0;
    }
    vector<int> aux;
    int con = 0;
    for(int i = 1;i <= n;i++){
        cin >> val[i] >> pai[i];
        if(pai[i] == 0){
            if(!aux.empty()){
                reverse(aux.begin(), aux.end());
                vector <pair <int, int>> res;
                int ac = 0;
                int mnac = 0;
                while(!aux.empty()){
                    // cout << aux.back() << ' ' << ac << '\n';
                    if(aux.back() + ac >= 0){
                        ac = 0;
                        res.push_back({aux.back()+ac, mnac});
                        mnac = 0;
                    }
                    else{
                        ac += aux.back();
                        mnac = min(mnac, ac);
                    }
                    aux.pop_back();
                }
                reverse(res.begin(), res.end());
                for(auto x : res){
                    //cout << x.first << ' ';
                    s[con].push(x);
                }
                con++;
            }
        }
        //cout << val[i] << ' ';
        aux.push_back(val[i]);
    }
    if(!aux.empty()){
        reverse(aux.begin(), aux.end());
        vector <pair <int, int>> res;
        int ac = 0;
        int mnac = 0;
        while(!aux.empty()){
            //cout << aux.back() << ' ';
            if(aux.back() + ac >= 0){
                //cout << aux.back() << ' ';
                res.push_back({aux.back()+ac, mnac});
                ac = 0;
                mnac = 0;
            }
            else{
                ac += aux.back();
                mnac = min(mnac, ac);
            }
            aux.pop_back();
        }
        reverse(res.begin(), res.end());
        for(auto x : res){
            //cout << x.first << ' ';
            s[con].push(x);
        }
        con++;
    }
    priority_queue <array <int, 3>> pq;
    for(int i = 0;i < con;i++){
        if(s[i].empty()) continue;
        pq.push({s[i].top().second, s[i].top().first, i});
    }
    int res = 0;
    while(!pq.empty()){
        auto [mnac, valtot, i] = pq.top();
        pq.pop();
        // cout << mnac << ' ';
        if(c + mnac < 0) break;
        res += valtot;
        c += valtot;
        s[i].pop();
        if(s[i].empty()) continue;
        pq.push({s[i].top().second, s[i].top().first, i});
    }
    cout << res << '\n';
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 224456 KB Output is correct
2 Correct 232 ms 223824 KB Output is correct
3 Correct 226 ms 223224 KB Output is correct
4 Correct 222 ms 229460 KB Output is correct
5 Correct 237 ms 232168 KB Output is correct
6 Correct 198 ms 221308 KB Output is correct
7 Correct 220 ms 223616 KB Output is correct
8 Correct 241 ms 223224 KB Output is correct
9 Correct 205 ms 231252 KB Output is correct
10 Correct 207 ms 232532 KB Output is correct
11 Correct 267 ms 223824 KB Output is correct
12 Correct 226 ms 222528 KB Output is correct
13 Correct 262 ms 223872 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 216284 KB Output is correct
2 Correct 85 ms 216468 KB Output is correct
3 Incorrect 85 ms 216404 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 216284 KB Output is correct
2 Correct 85 ms 216468 KB Output is correct
3 Incorrect 85 ms 216404 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 216284 KB Output is correct
2 Correct 85 ms 216468 KB Output is correct
3 Incorrect 85 ms 216404 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 224456 KB Output is correct
2 Correct 232 ms 223824 KB Output is correct
3 Correct 226 ms 223224 KB Output is correct
4 Correct 222 ms 229460 KB Output is correct
5 Correct 237 ms 232168 KB Output is correct
6 Correct 198 ms 221308 KB Output is correct
7 Correct 220 ms 223616 KB Output is correct
8 Correct 241 ms 223224 KB Output is correct
9 Correct 205 ms 231252 KB Output is correct
10 Correct 207 ms 232532 KB Output is correct
11 Correct 267 ms 223824 KB Output is correct
12 Correct 226 ms 222528 KB Output is correct
13 Correct 262 ms 223872 KB Output is correct
14 Correct 88 ms 216284 KB Output is correct
15 Correct 85 ms 216468 KB Output is correct
16 Incorrect 85 ms 216404 KB Output isn't correct
17 Halted 0 ms 0 KB -