Submission #1129002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129002		nhanhoang510	Jobs (BOI24_jobs)	C++20	11 / 100	124 ms	26948 KiB

Main

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxn = 3 * 1e5 + 7;
const int LOG = 20;
const long long MOD = (long long)(1e9) + 7;
const long long base = 311;
const int ALP_BET = 26;

typedef pair<int, int> ii;
typedef pair<int, long long> il;
typedef pair<long long, int> li;
typedef pair<long long, long long> ll;

int n, m;
long long a[maxn], s;
int p[maxn]; vector<int> adj[maxn];
int root[maxn];

namespace BUFFALO{

const int maxN = 10 + 7;
bool ok[maxN];
int arr[maxN];

long long ans;

void solve(){
    for(int i = 1; i <= n; ++i)
        arr[i] = i;
    ans = s;
    do{
        memset(ok, false, sizeof(ok));
        long long sum = s;
        for(int i = 1; i <= n; ++i){
            int u = arr[i];
            if(p[u] != 0 && !ok[p[u]])
                break;
            ok[u] = true;
            sum = sum + a[u];
            if(sum < 0)
                break;
            ans = max(ans, sum);
        }
    } while(next_permutation(arr + 1, arr + n + 1));
    cout << ans - s << "\n";
    return;
}

}

namespace SUB1{

long long dp[maxn];

void dfs(int u){
    dp[u] = a[u];
    for(int v : adj[u]){
        dfs(v);
        dp[u] = dp[u] + dp[v];
    }
    dp[u] = max(dp[u], 0LL);
    return;
}

void solve(){
    long long ans = 0;
    for(int i = 1; i <= m; ++i){
        dfs(root[i]);
        ans += dp[root[i]];
    }
    cout << ans << "\n";
    return;
}

}

namespace SUB3{

typedef pair<long long, long long> item;

int nn;
item path[maxn];

void dfs(int u, long long ss, long long maxadd, long long maxsub){
    ss = ss + a[u];
    if(ss > maxadd){
        ++nn;
        path[nn] = {maxsub, ss - maxadd};
        maxadd = ss;
    }
    maxsub = max(maxsub, -ss);
    if(!adj[u].empty()){
        dfs(adj[u][0], ss, maxadd, maxsub);
    }
    return;
}

void solve(){
    nn = 0;
    for(int i = 1; i <= m; ++i){
        int u = root[i];
        dfs(u, 0, 0, 0);
    }
//    cerr << nn << "\n";
//    for(int i = 1; i <= nn; ++i){
//        cerr << path[i].F << " " << path[i].S << "\n";
//    }
    long long ans = 0;
    sort(path + 1, path + nn + 1);
    for(int i = 1; i <= nn; ++i){
        long long limit = path[i].F, val = path[i].S;
        if(limit > s)
            break;
        ans = ans + val;
    }
    cout << ans << "\n";
    return;
}

}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // freopen("Jobs.INP","r",stdin);
    // freopen("Jobs.OUT","w",stdout);
    cin >> n >> s; m = 0;
    for(int i = 1; i <= n; ++i){
        cin >> a[i] >> p[i];
        if(p[i] == 0){
            ++m;
            root[m] = i;
        } else{
            adj[p[i]].push_back(i);
        }
    }
    bool sub1 = true;
    long long ss = s;
    for(int i = 1; i <= n; ++i) if(a[i] < 0){
        ss = ss + a[i];
    }
    if(ss < 0)
        sub1 = false;

    // SUBTASK
    if(n <= 10){
        BUFFALO::solve();
    } else
    if(sub1){
        SUB1::solve();
    } else
        SUB3::solve();
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31