Submission #829433

#	Time	Username	Problem	Language	Result	Execution time	Memory
829433		erray	Catfish Farm (IOI22_fish)	C++17	100 / 100	164 ms	23708 KiB

fish

#include "fish.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/eagle/ioi22/debug.h"
#else 
  #define debug(...) void(37)
#endif

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
  vector<int> ord(M);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int x, int y) {
    return pair{X[x], Y[x]} < pair{X[y], Y[y]};
  });
  vector<pair<int, vector<array<int, 2>>>> gs;
  vector<vector<long long>> pref;
  gs.emplace_back(-1, vector<array<int, 2>>{});
  pref.push_back(vector<long long>{0});
  for (int i = 0; i < M; ++i) {
    if (i == 0 || X[ord[i - 1]] != X[ord[i]]) {
      gs.emplace_back(X[ord[i]], vector<array<int, 2>>{});
      pref.push_back(vector<long long>{0});
    }
    gs.back().second.push_back({Y[ord[i]], W[ord[i]]});
    pref.back().push_back(pref.back().back() + W[ord[i]]);
  }
  gs.emplace_back(N, vector<array<int, 2>>{});
  pref.push_back(vector<long long>{0});
  debug(gs, pref);
  const long long inf = (long long) 1e16;
  vector<long long> inc(1, -inf);
  vector<long long> dec(1, -inf);
  vector<long long> valley(1, -inf);
  long long ans = 0;
  for (int i = 1; i < int(gs.size()); ++i) {
    auto& a = gs[i].second;
    //auto& next = gs[i + 1].second;
    auto& prev = gs[i - 1].second;
    int s = int(a.size());
    debug(a, prev);
    //int next_s = int(next.size());
    int prev_s = int(prev.size());
    vector<long long> new_inc(s + 1);
    vector<long long> new_dec(s + 1);
    vector<long long> new_valley(s + 1);
    vector<int> need(s + 1);
    int fop = -1;
    for (int j = 0; j < s; ++j) {
      while (fop + 1 < prev_s && prev[fop + 1][0] <= a[j][0]) {
        ++fop;
      }
      need[j + 1] = fop + 1;
    }
    vector<int> takes(s + 1);
    {
      int p = 0;
      for (int j = 0; j < s; ++j) {
        while (p < prev_s && prev[p][0] < a[j][0]) {
          ++p;
        }
        takes[j] = p;
      }
    }
    takes.back() = prev_s;
    debug(need, takes);
    if (gs[i].first != gs[i - 1].first + 1) {
      long long mx = 0;
      for (auto x : valley) {
        mx = max(mx, x + pref[i - 1].back());
      }
      for (int j = 0; j <= prev_s; ++j) {
        mx = max(mx, pref[i - 1].back() - pref[i - 1][j] + inc[j]);
      }
      ans += mx;
      for (int j = 0; j <= s; ++j) {
        new_valley[j] = 0;
      }
      for (int j = 0; j <= s; ++j) {
        new_dec[j] = pref[i].back() - pref[i][j];
      }
      for (int j = 0; j <= s; ++j) {
        new_inc[j] = 0;
      }
      debug(ans, new_valley, new_dec, new_inc);
    } else {
      //valley case
      {
        int p = prev_s;
        long long mx = -inf;
        for (int j = s; j >= 0; --j) {
          while (p >= need[j]) {
            mx = max({mx, dec[p], inc[p]});
            --p;
          }
          new_valley[j] = mx;
        }
      } 
      //inc
      {
        {
          long long mx = 0;
          long long val = 0;
          int p = 0;
          for (int j = 0; j <= s; ++j) {
            while (p <= takes[j]) {
              mx = max(mx, inc[p] - pref[i - 1][p]);
              val = max(val, valley[p]);
              ++p;
            }
            new_inc[j] = max(new_inc[j], max(val, mx) + pref[i - 1][takes[j]]); 
          }
        } 
        debug(new_inc);
        {
          long long down = 0;
          for (int j = 0; j <= prev_s; ++j) {
            down = max(down, pref[i - 1][j] + valley[j]);
          }
          for (int j = 0; j <= s; ++j) {
            new_inc[j] = max(new_inc[j], down);
          }
        }
      }
      //dec
      {
        int p = prev_s;
        long long prev_mx = -inf;
        for (int j = s; j >= 0; --j) {
          while (p >= need[j]) {
            prev_mx = max(prev_mx, max(inc[p], dec[p]) + pref[i][j]);
            --p;
          }
          new_dec[j] = max(0LL, prev_mx - pref[i][j]);
        }
      }
      debug(new_valley);
      debug(new_dec);
      debug(new_inc);
    }
    swap(inc, new_inc);
    swap(dec, new_dec);
    swap(valley, new_valley);
  }
  //dont forget the end case 
  debug(ans);
  return ans + dec[0]; 
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16