oj.uz

Submission #1073721

# Submission time Handle Problem Language Result Execution time Memory
1073721 2024-08-24T19:18:53 Z Gabriel Meetings (IOI18_meetings) C++17
21 / 100
 91 ms 20572 KB 
#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
vector<long long> h;
struct Nodo{
  long long r, p, s, suma;
};
vector<Nodo> _rbol;
Nodo Combinar(Nodo a, Nodo b){
  Nodo c;
  c.p = max(a.p, max(a.suma + b.p, 0LL));
  c.s = max(b.s, max(b.suma + a.s, 0LL));
  c.suma = a.suma + b.suma;
  c.r = max(max(a.r, 0LL), max(b.r, a.s + b.p));
  return c;
}
void Crear(long long i, long long f, long long p){
  if(i == f){
    _rbol[p].suma = h[i];
    _rbol[p].p = max(0LL, h[i]);
    _rbol[p].s = _rbol[p].p;
    _rbol[p].r = _rbol[p].p;
  } else {
    long long P = (i + f) / 2;
    Crear(i, P, p * 2);
    Crear(P + 1, f, p * 2 + 1);
    _rbol[p] = Combinar(_rbol[p * 2], _rbol[p * 2 + 1]);
  }
}
Nodo C(long long i, long long f, long long p, long long I, long long D){
  if(i >= I and f <= D) return _rbol[p];
  if(i > D or f < I){
    Nodo AAA;
    AAA.p = -2222LL;
    AAA.s = -2222LL;
    AAA.suma = -2222LL;
    AAA.r = -2222LL;
    return AAA;
  }
  long long P = (i + f) / 2;
  return Combinar(C(i, P, p * 2, I, D), C(P + 1, f, p * 2 + 1, I, D));
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
  vector<long long> l, r;
  bool _3 = 1;
  long long n = H.size();
  long long q = L.size();
  for(long long i = 0; i < n; i++){
    h.push_back((long long)H[i]);
    if(h[i] != 1 and h[i] != 2) _3 = 0;
  }
  for(long long i = 0; i < q; i++) l.push_back((long long)L[i]);
  for(long long i = 0; i < q; i++) r.push_back((long long)R[i]);
  vector<long long> c(q);
  if(_3){
    Nodo a;
    a.r = -2222LL;
    a.p = -2222LL;
    a.s = -2222LL;
    a.suma = -2222LL; 
    _rbol.assign(n * 4 + 22, a);
    for(long long i = 0; i < n; i++){
      if(h[i] == 2LL) h[i] = -2222LL;
    }
    n--;
    Crear(0, n, 1);
    for(long long i = 0; i < q; i++){
      c[i] = (r[i] - l[i] + 1LL) * 2 - C(0, n, 1, l[i], r[i]).r;
    }
  } else if(n <= 3022 and q <= 12){
    for(long long i = 0; i < q; i++){
      long long Bien = LLONG_MAX;
      for(long long j = l[i]; j <= r[i]; j++){
        long long Costo = h[j];
        long long Mayor = h[j];
        for(long long k = j - 1; k >= l[i]; k--){
          Mayor = max(Mayor, h[k]);
          Costo += Mayor;
        }
        Mayor = h[j];
        for(long long k = j + 1; k <= r[i]; k++){
          Mayor = max(Mayor, h[k]);
          Costo += Mayor;
        }
        if(Costo < Bien) Bien = Costo;
      }
      c[i] = Bien;
    }
  } 
  return c;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 59 ms 492 KB Output is correct
4 Correct 19 ms 344 KB Output is correct
5 Correct 59 ms 488 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 59 ms 348 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 59 ms 492 KB Output is correct
4 Correct 19 ms 344 KB Output is correct
5 Correct 59 ms 488 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 59 ms 348 KB Output is correct
10 Incorrect 2 ms 604 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 30 ms 3544 KB Output is correct
3 Correct 91 ms 20428 KB Output is correct
4 Correct 87 ms 20432 KB Output is correct
5 Correct 62 ms 20376 KB Output is correct
6 Correct 79 ms 20572 KB Output is correct
7 Correct 88 ms 20440 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 30 ms 3544 KB Output is correct
3 Correct 91 ms 20428 KB Output is correct
4 Correct 87 ms 20432 KB Output is correct
5 Correct 62 ms 20376 KB Output is correct
6 Correct 79 ms 20572 KB Output is correct
7 Correct 88 ms 20440 KB Output is correct
8 Incorrect 41 ms 7884 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 59 ms 492 KB Output is correct
4 Correct 19 ms 344 KB Output is correct
5 Correct 59 ms 488 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 59 ms 348 KB Output is correct
10 Incorrect 2 ms 604 KB Output isn't correct
11 Halted 0 ms 0 KB -