Submission #1234468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234468		asdfgrace	Jobs (BOI24_jobs)	C++20	0 / 100	56 ms	324 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) //x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define parr(x) dbg(cerr << #x << " = "; for (auto y : x) {cerr << y << ' ';} cerr << '\n';)
#define parr2d(x) dbg(cerr << #x << " = \n"; for (auto _ : x) {parr(_);} cerr << '\n';)

/*
if there are cycles, just don't consider them
they will stand out and not be connected to node 0

note that this is like a tree
you start from node 0 & can have multiple traversors, but you must go down the tree step by step
answer to subtask 1 is just the maximum smth idk
if you have a series of paths
then you can interleave them
anyway
paths can be condensed into alternating positives and negatives
you're gonna greedily absorb as many positives as possible
then when there are no positives
everything is blocked by a negative
how do you decide which one?
ok now each path has a maximum prefix sum
you don't want to take ANYTHING beyond that for any path
and let's say the path has a number of minimum prefix sums
and a number of maximum prefix sums
you will ensure that the amount you take is A maximum even if isn't THE maximum
so what if we consider this a path between maximum prefix sums & other maximum prefix sums
so you can do a topsort of the graph
find the topsort such that no prefix sum is less than ---
(only up to a certain point)
and the maximum prefix sum is maximal

if this is a greedy:
"cut off" each path AFTER the maximum prefix sum (i.e. pop back)
let's say you have max prefix sum & then it's 0 at some point
which means it dips back down & comes back
that's not worth it
if multiple occs of max pref sum
only take the earliest
if you can take any positives at this time, take it
if you can only take negatives at this time - how do you choose?
consider each negative & the profit if you take the positive that follows
take the negative you can take that will generate the biggest profit following it
that's guaranteed to help
so even if you don't reach the end of that
you still made as much profit as you could have
so yeah
maybe you do a set of loss/reward pairs, which is very ez in n^2
but how can you query "biggest reward given the loss <= this"?
the values are very big
but after condensing
there are at most N values of loss
so you can just do a segtree or smth

now what if everything is negative (no positive profits)?
for segments for which you won't gain profit at any point
maybe from each point you end on a positive & go to negative
if the profit is positive
take it
otherwise, keep a running profit & keep a running minimum prefix sum
then you can mark the cost of that segment as {minimum prefix sum, total profit}

8 2
3 0
-3 1
-2 2
0 3
-1 4
8 5
-1 0
2 7
*/

int sign(long long x) {
  return (x == 0 ? 0 : (x > 0 ? 1 : -1));
}

struct Segtree {
  int n;
  vector<array<long long, 2>> a;
  
  Segtree (int x) {
    n = x;
    a.resize(2 * n);
    for (int i = 0; i < 2 * n; i++) {
      a[i] = {(long long) -1e18, i};
    }
  }
  
  void upd(int k, long long x) {
    pv(k); pv(x);
    k += n;
    a[k] = {x, k};
    for (int i = k / 2; i > 0; i /= 2) {
      a[i] = max(a[2 * i], a[2 * i + 1]);
    }
  }
  
  array<long long, 2> quer(int l, int r) {
    l += n; r += n;
    array<long long, 2> res = {(long long) -1e18, 0};
    while (r >= l) {
      if (l % 2 == 1) res = max(res, a[l++]);
      if (r % 2 == 0) res = max(res, a[r--]);
      l /= 2; r /= 2;
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int _n; long long s;
  cin >> _n >> s;
  long long init = s;
  vector<vector<array<long long, 2>>> a;
  int n = 0;
  for (int i = 0; i < _n; i++) {
    pv(i);
    long long x, p;
    cin >> x >> p;
    if (p == 0) {
      a.push_back(vector<array<long long, 2>>());
      n++;
      a[n - 1].push_back({0, 0}); // minimum prefix sum, maximum prefix sum
    }
    if (a[n - 1].back()[1] > 0 && x < 0) {
      a[n - 1].push_back({x, x});
    } else {
      a[n - 1].back()[1] += x;
      a[n - 1].back()[0] = min(a[n - 1].back()[0], a[n - 1].back()[1]);
    }
  }
  for (int i = 0; i < n; i++) {
    parr2d(a[i]);
  }
  vector<array<long long, 3>> neg;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < (int) a[i].size(); j++) {
      neg.push_back({-a[i][j][0], i, j});
    }
  }
  int m = neg.size();
  sort(neg.begin(), neg.end());
  vector<vector<int>> at(n);
  for (int i = 0; i < n; i++) {
    at[i].resize(a[i].size());
  }
  for (int i = 0; i < m; i++) {
    at[neg[i][1]][neg[i][2]] = i;
  }
  parr2d(neg);
  parr2d(at);
  vector<int> it(n, 0);
  Segtree st(m);
  for (int i = 0; i < n; i++) {
    st.upd(at[i][0], a[i][0][1]);
  }
  long long mx = 0;
  int asdf = 3;
  while (asdf--) {
    parr2d(st.a);
    array<long long, 3> tmp = {s, (long long) 1e18, (long long) 1e18};
    int lb = upper_bound(neg.begin(), neg.end(), tmp) - neg.begin() - 1;
    pv(lb);
    if (lb == -1) break;
    array<long long, 2> res = st.quer(0, lb);
    parr(res);
    if (res[0] < 0) break;
    s += res[0];
    int ind = res[1] - m;
    it[neg[ind][1]]++;
    st.upd(ind, -1e18);
    if (it[neg[ind][1]] < a[neg[ind][1]].size()) {
      st.upd(at[neg[ind][1]][it[neg[ind][1]]], a[neg[ind][1]][it[neg[ind][1]]][1]);
    }
    mx = max(mx, s - init);
    pv(s); prt('\n');
  }
  cout << mx << '\n';
}

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