Submission #1194626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194626		LucaLucaM	Meetings (IOI18_meetings)	C++20	19 / 100	5594 ms	5836 KiB

meetings

#include "meetings.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

#define debug(x) #x << " = " << x  << '\n';

using ll = long long;

const ll INF = 1e18;

std::vector<ll> minimum_costs(std::vector<int> a, std::vector<int> L, std::vector<int> R) {
  int n = (int) a.size();
  int q = (int) L.size();

  std::vector<ll> answer(q, +INF);

  std::vector<ll> pref(n);

  auto solve = [&](auto &self, int l, int r) -> void {
    if (l > r) {
      return;
    }

    int p = l;
    for (int i = l + 1; i <= r; i++) {
      if (a[i] > a[p]) {
        p = i;
      }
    }


    
    self(self, l, p - 1);
    self(self, p + 1, r);

    // raspund la query uri
    for (int i = 0; i < q; i++) {
      if (l <= L[i] && L[i] <= p && p <= R[i] && R[i] <= r) {
        answer[i] = std::min(answer[i], pref[R[i]] + (ll) a[p] * (p - L[i] + 1));
      }
    }

    // acum trebuie sa recalculez pref[l..r]
    // pref[l..p-1] ramane la fel
    // pref[p]
    ll c = p == l? 0 : pref[p - 1];
    pref[p] = c + a[p];
    // pref[p+1..r] 
    for (int i = p + 1; i <= r; i++) {
      pref[i] += (ll) a[p] * (p - l + 1);
    }
    for (int i = p + 1; i <= r; i++) {
      pref[i] = std::min(pref[i], c + (ll) a[p] * (i - p + 1));
    }
  }; 

  solve(solve, 0, n - 1);
  std::reverse(a.begin(), a.end());
  for (int i = 0; i < q; i++) {
    L[i] = n - 1 - L[i];
    R[i] = n - 1 - R[i];
    std::swap(L[i], R[i]);
  }
  solve(solve, 0, n - 1);

  return answer;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40