Submission #790091

#	Time	Username	Problem	Language	Result	Execution time	Memory
790091		gesgha	Catfish Farm (IOI22_fish)	C++17	70 / 100	799 ms	469200 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 = 3000;
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];

bool vs[M][M];

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
  // #ifdef local
  // freopen("output.txt", "w", stdout);
  // #endif
  if(N <= 4e3) {
    for (int i = 0; i < M; i++) {
      vs[X[i]][Y[i]] = 1;
    }
    for (int i  = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (!vs[i][j]) {
          X.pb(i);
          Y.pb(j);
          W.pb(0);
        }
      }
    }
  }

  for (int i = 0; i < sz(Y); 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++) {
    // from dp1
    { // to zero 
      int Z = 0;
      ll S = 0;
      for (int j = 0; j < sz(YY[i - 1]); j++) {
        while(Z < sz(YY[i]) && YY[i - 1][j].fi - 1 >= YY[i][j].fi) {
          S += YY[i][Z].se;
          Z++;
        }
        umx(zero[i][Z], dp1[i - 1][j] + S);
      }
      for (; Z < sz(YY[i]); Z++) {
        S += YY[i][Z].se;
      }
      umx(zero[i].back(), dp1[i - 1].back() + S);
    }
    { // to dp1
      umx(dp1[i].back(), dp1[i - 1].back());
      ll 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
      { // back
        ll S = 0;
        for (int j = sz(YY[i - 1]); j >= 0; j--) {
          umx(dp1[i].back(), S + zero[i - 1][j]);
          umx(dp2[i].back(), S + zero[i - 1][j]);
          if (j - 1 >= 0) S += YY[i - 1][j - 1].se;
        }
      }
      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].se;
          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 S = 0;
      for (int j = 0; j < sz(YY[i - 1]); j++) {
        while(Z < sz(YY[i]) && YY[i - 1][j].fi - 1 >= YY[i][j].fi) {
          S += YY[i][Z].se;
          Z++;
        }
        umx(zero[i][Z], dp2[i - 1][j] + S);
      }
      for (; Z < sz(YY[i]); Z++) {
        S += YY[i][Z].se;
      }
      umx(zero[i].back(), dp2[i - 1].back() + S);
    }
    { // to dp2 & dp1
      ll S = 0;
      ll mx = 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) {
          umx (mx, dp2[i - 1][ptr] - S);
          S += YY[i - 1][ptr].se;
          ptr++;
        }
        umx(dp2[i][j], mx + S);
        umx(dp1[i][j], mx + S);
      }
      for (; ptr < sz(YY[i - 1]); ptr++) {
        umx(mx, dp2[i - 1][ptr] - S);
        S += YY[i - 1][ptr].se;
      }
      umx(mx, dp2[i - 1].back() - S);
      umx(dp2[i].back(), mx + S);
      umx(dp1[i].back(), mx + S);
    }
  }
  // cout << zero[2][1] << endl;
  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: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16