Submission #778181

#	Time	Username	Problem	Language	Result	Execution time	Memory
778181		NeroZein	Meetings (IOI18_meetings)	C++17	19 / 100	5550 ms	7648 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"
using namespace std; 

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int q = L.size();
  auto go = [&](int l, int r) {
    vector<int> a(r - l + 1);
    for (int i = l; i <= r; ++i) {
      a[i - l] = H[i]; 
    }
    vector<long long> in(r - l + 1);
    for (int it = 0; it < 2; ++it) {
      long long res = 0; 
      stack<pair<int, int>> stk; //element, occ
      for (int i = 0; i < (int) a.size(); ++i) {
        int c = 1; 
        while (!stk.empty() && stk.top().first < a[i]) {
          res -= (long long) stk.top().first * stk.top().second;
          c += stk.top().second;
          stk.pop();
        }
        res += (long long) a[i] * c;
        stk.push({a[i], c}); 
        in[i] += res; 
      }
      reverse(a.begin(), a.end());
      reverse(in.begin(), in.end()); 
    }
    long long mn = LLONG_MAX;
    for (int i = 0; i < (int) a.size(); ++i) {
      mn = min(mn, in[i] - a[i]);
    }
    return mn;
  };
  vector<long long> ans(q); 
  for (int i = 0; i < q; ++i) {
    ans[i] = go(L[i], R[i]); 
  }
  return ans;
}

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