Submission #1035208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035208		NeroZein	Meetings (IOI18_meetings)	C++17	19 / 100	5541 ms	7896 KiB

meetings

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

vector<int> h, ql, qr;

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  h = H; ql = L, qr = R;
  int n = (int) H.size();
  int q = (int) L.size();
  vector<long long> ret(q, LLONG_MAX); 
  for (int qind = 0; qind < q; ++qind) {
    stack<pair<int, int>> stk; //element, occurrence
    long long res = 0;
    vector<long long> ans(n);
    for (int i = ql[qind]; i <= qr[qind]; ++i) {
      int f = 1;
      while (!stk.empty() && stk.top().first < h[i]) {
        auto [element, cnt] = stk.top();
        stk.pop();
        f += cnt;
        res -= (long long) element * cnt; 
      }
      stk.push({h[i], f});
      res += (long long) h[i] * f;
      ans[i] = res;
    }
    while (!stk.empty()) {
      stk.pop();
    }
    res = 0;
    for (int i = qr[qind]; i >= ql[qind]; --i) {
      int f = 1;
      while (!stk.empty() && stk.top().first < h[i]) {
        auto [element, cnt] = stk.top();
        stk.pop();
        f += cnt;
        res -= (long long) element * cnt; 
      }
      stk.push({h[i], f});
      res += (long long) h[i] * f;
      ans[i] += res - h[i]; 
      ret[qind] = min(ret[qind], ans[i]);
    }
  }
  return ret; 
}

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