Submission #1223247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223247		Gabriel	Nile (IOI24_nile)	C++20	36 / 100	2093 ms	18360 KiB

nile

#include "nile.h"
#include "bits/stdc++.h"
using namespace std;
struct Artefacto{
  long long Peso, a, b;
};
bool Primero = 1, Segundo = 1, Tercero = 1;
bool operator<(const Artefacto& a, const Artefacto& b){
  if(Primero) return a.a - a.b > b.a - b.b;
  if(Segundo or Tercero) return a.Peso < b.Peso;
}
vector<Artefacto> Per__es_clave;
vector< vector<long long> > PD;
long long Resolver(long long i, long long Saltado){
  if(i == Per__es_clave.size()){
    if(Saltado == 1) return 0;
    else return 2222222222222222;
  }
  if(i == Per__es_clave.size() - 1) return Per__es_clave[i].a;
  if(PD[i][Saltado] != -2) return PD[i][Saltado];
  return PD[i][Saltado] = min(Resolver(i + 2, Saltado) + Per__es_clave[i].b + Per__es_clave[i + 1].b, Resolver(i + 1, 1) + Per__es_clave[i].a);
}
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
  int n = a.size(), q = e.size();
  for(long long i = 0; i < n; i++){
    Artefacto Nuevo;
    Nuevo.Peso = w[i];
    if(w[i] != 1) Primero = 0;
    if(w[i] != i + 1) Segundo = 0;
    if(a[i] != 2 or b[i] != 1) Tercero = 0;
    Nuevo.a = a[i];
    Nuevo.b = b[i];
    Per__es_clave.push_back(Nuevo);
  }
  sort(Per__es_clave.begin(), Per__es_clave.end());
  long long r = 0;
  if(Primero){
    for(long long i = 0; i < n; i++){
      if(i + 1 == n) r += Per__es_clave[i].a;
      else r += Per__es_clave[i].b + Per__es_clave[i + 1].b;
      i++;
    }
    return vector<long long>(q, r);
  }
  if(Segundo){
    long long Menor = 2222222222222222;
    for(long long i = 0; i < n; i++){
      Menor = min(Per__es_clave[i].a - Per__es_clave[i].b, Menor);
      r += Per__es_clave[i].b;
    }
    PD.assign(n, vector<long long>(2, -2));
    if(n % 2 == 0) return vector<long long>(q, r);
    else {
      vector<long long> Retorno;
      for(long long i = 0; i < q; i++){
        long long v = e[i];
        //cerr<<v<<"\n";
        if(v >= 2) Retorno.push_back(r + Menor);
        else Retorno.push_back(Resolver(0, 0));
      }
      return Retorno;
    }
  }
  if(Tercero){
    vector<long long> Retorno;
    for(auto E: e){
      r = 0;
      for(long long i = 0; i < n; i++){
        if(i == n - 1) r += Per__es_clave[i].a;
        else {
          if(abs(Per__es_clave[i].Peso - Per__es_clave[i + 1].Peso) <= E){
            r += Per__es_clave[i].b + Per__es_clave[i + 1].b;
            i++;
          } else r += Per__es_clave[i].a;
        }
      }
      Retorno.push_back(r);
    }
    return Retorno;
  }
}

Compilation message (stderr)

nile.cpp: In function 'bool operator<(const Artefacto&, const Artefacto&)':
nile.cpp:11:1: warning: control reaches end of non-void function [-Wreturn-type]
   11 | }
      | ^
nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18