Submission #789734

#	Time	Username	Problem	Language	Result	Execution time	Memory
789734		gesgha	Catfish Farm (IOI22_fish)	C++17	0 / 100	53 ms	23972 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = a; i <= b; i++)
#define rf(i, a, b) for (int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
  
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()
  
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
using ve = vector<T>;
 
template <typename T>
bool umx(T& a, T b) {
    return a < b ? a = b, 1 : 0;
}
 
template <typename T>
bool umn(T& a, T b) {
    return a > b ? a = b, 1 : 0;
}
 
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
 
const int oo = 1e9;
const ll OO = 1e18;
const int N = 1e5 + 100;
const int M = 2100;
const int K = 110;
const int mod = 1e9 + 7;
const bool TEST = 1;

void precalc() {}

ve <ll> dp1[N]; // before the i-th is filled, back -- all filled
ve <ll> dp2[N]; // before the i-th is filled, back -- all filled
ve <ll> zero[N]; // i points is used
ve <pii> YY[N];

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
  for (int i = 0; i < M; i++) {
    dp1[X[i]].pb(-OO);
    dp2[X[i]].pb(-OO);
    zero[X[i]].pb(-OO);
    YY[X[i]].pb({Y[i], W[i]});
  }
  for (int i = 0; i < N; i++) {
    sort(all(YY[i]));
    dp1[i].pb(-OO);
    dp2[i].pb(-OO);
    zero[i].pb(-OO);
  }
  for (int i = 0; i < sz(dp1[0]); i++) {
    dp1[0][i] = 0;
    dp2[0][i] = 0;
    zero[0][i] = 0;
  }
  for (int i = 1; i < N; i++) {
    // cout << i << endl;
    // from dp1
    { // to zero 
      int Z = 0;
      ll mx = -OO;
      for (int j = 0; j < sz(YY[i]); j++) {
        while (Z < sz(YY[i - 1]) && YY[i - 1][Z].fi < YY[i][j].fi) {
          mx = max(mx, dp1[i - 1][Z]);
          Z++;
        }
        umx(zero[i][j], mx);
      }
      for (; Z <= sz(YY[i - 1]); Z++) {
          umx(zero[i].back(), max(mx, dp1[i][Z]));
      }
    }
    { // to dp1
      umx(dp1[i].back(), dp1[i - 1].back());
      ll S = 0;
      for (int j = sz(YY[i - 1]); j >= 0; j--) {
        if (j < sz(YY[i - 1])) S += YY[i - 1][j].se;
        umx(dp1[i].back(), S + zero[i - 1][j]);
      }

      S = 0;
      int ptr = sz(YY[i - 1]) - 1;
      ll mx = dp1[i - 1].back();
      for (int j = sz(YY[i]) - 1; j >= 0; j--) {
        S += YY[i][j].se;
        while(ptr >= 0 && YY[i - 1][ptr].fi >= YY[i][j].fi) {
          mx = max(mx, dp1[i - 1][ptr] - S);
          ptr--;
        }
        umx(dp1[i][j], mx + S);
      }
    }
    
    // from zero    
    for (int j = 0; j <= sz(YY[i - 1]); j++) umx(zero[i][0], zero[i - 1][j]); // to zero
    { // to dp1 & dp2
      ll res = 0;
      for (int j = 0; j <= sz(YY[i - 1]); j++) umx(res, zero[i - 1][j]);
      ll S = 0;
      ll mx = zero[i - 1][0];
      int ptr = 0;
      for (int j = 0; j < sz(YY[i]); j++) {
        while(ptr < sz(YY[i - 1]) && YY[i - 1][ptr].fi < YY[i][j].fi - 1) {
          S += YY[i - 1][ptr].fi;
          ptr++;
          umx (mx, zero[i - 1][ptr] - S);
        }
        umx(dp1[i][j], max(res, mx + S));
        umx(dp2[i][j], max(res, mx + S));
      }
    }
    // from dp2
    { // to zero
      int Z = 0;
      ll mx = -OO;
      for (int j = 0; j < sz(YY[i]); j++) {
        while(Z < sz(YY[i - 1]) && YY[i - 1][Z].fi < YY[i][j].fi) {
          mx = max(mx, dp2[i - 1][Z]);
          Z++;
        }
        umx(zero[i][j], mx);
      }
      for (; Z <= sz(YY[i - 1]); Z++) {
          umx(zero[i].back(), max(mx, dp2[i][Z]));
      }
    }
    { // to dp2 & dp1
      ll S = 0;
      ll mx = -OO;
      int ptr = 0;
      for (int j = 0; j < sz(YY[i]); j++) {
        while (ptr < sz(YY[i - 1]) && YY[i - 1][ptr].fi <= YY[i][j].fi - 1) {
          umx (mx, dp2[i - 1][ptr] - S);
          S += YY[i - 1][ptr].fi;
          ptr++;
        }
        umx(dp2[i][j], mx + S);
        umx(dp1[i][j], mx + S);
      }
    }
  }
  ll ans = 0;
  fe(x, dp1[N - 1]) {
    umx(ans, x);
  }
  fe(x, dp2[N - 1]) {
    umx(ans, x);
  }
  fe(x, zero[N - 1]) {
    umx(ans, x);
  }
  return ans;
}

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