Submission #1311686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311686		kevinshenshiqi	Jobs (BOI24_jobs)	C++20	0 / 100	135 ms	9740 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct fen{
  vector <ll> bit;
  ll n;
  
  fen(ll _n){
    n = _n;
    bit = vector <ll>(n+1, -1e18);
  }
  
  //range max pt update fenwick tree
  void upd(ll f, ll v){
    while (f <= n){
      bit[f] = max(bit[f], v);
      f += (f&(-f));
    }
  }
  
  ll qry(ll f){
    ll maximum = -1e18;
    while (f > 0){
      maximum = max(maximum, bit[f]);
      f -= (f&(-f));
    }
    return maximum;
  }
};

int main() 
{
    ll n, s;
    cin >> n >> s;
    
    vector <ll> dp(n+1, -1e18);
    
    ll cost[n+1], pre[n+1];
    for (ll i = 1; i <= n; ++i){
      cin >> cost[i] >> pre[i];
    }
    
    fen* tree = new fen(n);
    
    ll runningMax = 0;
    
    for (ll i = 1; i <= n; ++i){
      ll dpVal = 0;
      if (pre[i] == 0) dpVal = tree->qry(n);
      else dpVal = dp[pre[i]];
      dpVal = max(dpVal + cost[i], cost[i]);
      dp[i] = dpVal;
      tree->upd(i, dpVal);
      runningMax = max(runningMax, dp[i]);
    }
    
    cout << max(s+runningMax, s) << "\n";
}

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