Submission #1238850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238850		Gabriel	Catfish Farm (IOI22_fish)	C++20	0 / 100	61 ms	19632 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
int Capas, Mayor;
struct Pez{
  int x, y;
  long long Valor;
};
vector< vector<Pez> > Puntos;
vector< map< long long, unordered_map<long long, long long> > > PD;
set< pair< pair<long long, long long>, long long> > Hay;
long long Resolver(int i, int Altura_anterior, int Altura_actual){
  int n = Puntos[i].size();
  if(i == Capas) return 0;
  if(Hay.count({{i, Altura_anterior}, Altura_actual}) != 0) return PD[i][Altura_anterior][Altura_actual];
  int x = Puntos[i][0].x, Izquierda = 0, Derecha = n - 1, Mejor_actual = n, Mejor_ambos = n;
  while(1){
    int Promedio = (Izquierda + Derecha) / 2;
    if(Altura_actual >= Puntos[i].back().y) break;
    if(Altura_actual < Puntos[i][Promedio].y){
      Mejor_actual = Promedio;
      Derecha = Promedio - 1;
    } else Izquierda = Promedio + 1;
    if(Izquierda >= Derecha + 1) break;
  }
  Izquierda = 0, Derecha = n - 1;
  while(1){
    int Promedio = (Izquierda + Derecha) / 2;
    if(max(Altura_actual, Altura_anterior) >= Puntos[i].back().y) break;
    if(max(Altura_actual, Altura_anterior) < Puntos[i][Promedio].y){
      Mejor_ambos = Promedio;
      Derecha = Promedio - 1;
    } else Izquierda = Promedio + 1;
    if(Izquierda >= Derecha + 1) break;
  }
  if(i == Capas - 1){
    if(x < Mayor){
      long long Suma = 0;
      for(; Mejor_ambos < n; Mejor_ambos++) Suma += Puntos[i][Mejor_ambos].Valor;
      Hay.insert({{i, Altura_anterior}, Altura_actual});
      return PD[i][Altura_anterior][Altura_actual] = Suma;
    } else {
      Hay.insert({{i, Altura_anterior}, Altura_actual});
      return PD[i][Altura_anterior][Altura_actual] = 0;
    }
  } else {
    if(i + 2 < Capas){
      if(Puntos[i + 1][0].x == x + 2){
        int m = Puntos[i + 1].size();
        long long Suma = 0, Mayor = 0;
        vector<int> Opciones;
        for(int j = 0; j < n; j++) Opciones.push_back(Puntos[i][j].y);
        for(int j = 0; j < m; j++) Opciones.push_back(Puntos[i + 1][j].y);
        sort(Opciones.begin(), Opciones.end());
        int j = 0, k = 0;
        for(auto E: Opciones){
          if(j < n and E >= Puntos[i][j].y){
            if(Puntos[i][j].y > max(Altura_actual, Altura_anterior)) Suma += Puntos[i][j].Valor;
            j++;
          }
          if(k < m and E >= Puntos[i + 1][k].y){
            Suma += Puntos[i + 1][k].Valor;
            k++;
          }
          Mayor = max(Mayor, Resolver(i + 1, E, -1) + Suma);
        }
        Hay.insert({{i, Altura_anterior}, Altura_actual});
        return PD[i][Altura_anterior][Altura_actual] = Mayor;
      } else if(Puntos[i + 2][0].x == x + 2){
        int m = Puntos[i + 2].size(), mm = Puntos[i + 1].size();
        long long Suma = 0, Mayor = 0;
        vector<int> Opciones;
        for(int j = 0; j < n; j++) Opciones.push_back(Puntos[i][j].y);
        for(int j = 0; j < mm; j++) Opciones.push_back(Puntos[i + 1][j].y);
        for(int j = 0; j < m; j++) Opciones.push_back(Puntos[i + 2][j].y);
        sort(Opciones.begin(), Opciones.end());
        int j = 0, k = 0, l = 0;
        for(auto E: Opciones){
          if(j < n and E >= Puntos[i][j].y){
            if(Puntos[i][j].y > max(Altura_actual, Altura_anterior)) Suma += Puntos[i][j].Valor;
            j++;
          }
          if(k < m and E >= Puntos[i + 2][k].y){
            Suma += Puntos[i + 2][k].Valor;
            k++;
          }
          if(l < mm and E >= Puntos[i + 1][l].y){
            if(Puntos[i + 1][l].y <= Altura_actual) Suma -= Puntos[i + 1][l].Valor;
            l++;
          }
          Mayor = max(Mayor, Resolver(i + 1, Altura_actual, E) + Suma);
        }
        Hay.insert({{i, Altura_anterior}, Altura_actual});
        return PD[i][Altura_anterior][Altura_actual] = Mayor;
      } else if(Puntos[i + 1][0].x == x + 1){
        int m = Puntos[i + 1].size();
        long long Suma = 0, Mayor = 0;
        vector<int> Opciones;
        for(int j = 0; j < n; j++) Opciones.push_back(Puntos[i][j].y);
        for(int j = 0; j < m; j++) Opciones.push_back(Puntos[i + 1][j].y);
        sort(Opciones.begin(), Opciones.end());
        int j = 0, k = 0;
        for(auto E: Opciones){
          if(j < n and E >= Puntos[i][j].y){
            if(Puntos[i][j].y > max(Altura_actual, Altura_anterior)) Suma += Puntos[i][j].Valor;
            j++;
          }
          if(k < m and E >= Puntos[i + 1][k].y){
            if(Puntos[i + 1][k].y <= Altura_actual) Suma -= Puntos[i + 1][k].Valor;
            k++;
          }
          Mayor = max(Mayor, Resolver(i + 1, Altura_actual, E) + Suma);
        }
        Hay.insert({{i, Altura_anterior}, Altura_actual});
        return PD[i][Altura_anterior][Altura_actual] = Mayor;
      } else {
        long long Suma = 0;
        for(; Mejor_ambos < n; Mejor_ambos++) Suma += Puntos[i][Mejor_ambos].Valor;
        Hay.insert({{i, Altura_anterior}, Altura_actual});
        return PD[i][Altura_anterior][Altura_actual] = Suma + Resolver(i + 1, -1, -1);
      }
    }
    if(Puntos[i + 1][0].x == x + 2){
      int m = Puntos[i + 1].size();
      long long Suma = 0, Mayor = 0;
      vector<int> Opciones;
      for(int j = 0; j < n; j++) Opciones.push_back(Puntos[i][j].y);
      for(int j = 0; j < m; j++) Opciones.push_back(Puntos[i + 1][j].y);
      sort(Opciones.begin(), Opciones.end());
      int j = 0, k = 0;
      for(auto E: Opciones){
        if(j < n and E >= Puntos[i][j].y){
          if(Puntos[i][j].y > max(Altura_actual, Altura_anterior)) Suma += Puntos[i][j].Valor;
          j++;
        }
        if(k < m and E >= Puntos[i + 1][k].y){
          Suma += Puntos[i + 1][k].Valor;
          k++;
        }
        Mayor = max(Mayor, Resolver(i + 1, E, -1) + Suma);
      }
      Hay.insert({{i, Altura_anterior}, Altura_actual});
      return PD[i][Altura_anterior][Altura_actual] = Mayor;
    } else if(Puntos[i + 1][0].x == x + 1){
      int m = Puntos[i + 1].size();
      long long Suma = 0, Mayor = 0;
      vector<int> Opciones;
      for(int j = 0; j < n; j++) Opciones.push_back(Puntos[i][j].y);
      for(int j = 0; j < m; j++) Opciones.push_back(Puntos[i + 1][j].y);
      sort(Opciones.begin(), Opciones.end());
      int j = 0, k = 0;
      for(auto E: Opciones){
        if(j < n and E >= Puntos[i][j].y){
          if(Puntos[i][j].y > max(Altura_actual, Altura_anterior)) Suma += Puntos[i][j].Valor;
          j++;
        }
        if(k < m and E >= Puntos[i + 1][k].y){
          if(Puntos[i + 1][k].y <= Altura_actual) Suma -= Puntos[i + 1][k].Valor;
          k++;
        }
        Mayor = max(Mayor, Resolver(i + 1, Altura_actual, E) + Suma);
      }
      Hay.insert({{i, Altura_anterior}, Altura_actual});
      return PD[i][Altura_anterior][Altura_actual] = Mayor;
    } else {
      long long Suma = 0;
      for(; Mejor_ambos < n; Mejor_ambos++) Suma += Puntos[i][Mejor_ambos].Valor;
      Hay.insert({{i, Altura_anterior}, Altura_actual});
      return PD[i][Altura_anterior][Altura_actual] = Suma + Resolver(i + 1, -1, -1);
    }
  }
}
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
  Mayor = m - 1;
  vector< pair< pair<int, int>, int> > Pez_causas(n);
  for(int i = 0; i < n; i++) Pez_causas[i] = {{x[i], y[i]}, w[i]};
  sort(Pez_causas.begin(), Pez_causas.end());
  //cerr<<"Orden.\n";
  map< long long, unordered_map<long long, long long> > A;
  for(auto E: Pez_causas){
    Pez Actual;
    Actual.x = E.first.first;
    Actual.y = E.first.second;
    Actual.Valor = E.second;
    if(Puntos.size() > 0 and Puntos.back().size() > 0 and Puntos.back()[0].x == Actual.x) Puntos.back().push_back(Actual);
    else Puntos.push_back({Actual});
  }
  Capas = Puntos.size();
  PD.assign(Capas, A);
  //cerr<<"A trabajar.\n";
  return Resolver(0, -1, -1);
}

• 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