Submission #603985

#	Time	Username	Problem	Language	Result	Execution time	Memory
603985		erekle	Meetings (IOI18_meetings)	C++17	19 / 100	5528 ms	7056 KiB

meetings

#include "meetings.h"
#include <stack>
#include <algorithm>
#include <iostream>

using namespace std;

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  int Q = L.size();
  vector<long long> C(Q);
  for (int q = 0; q < Q; ++q) {
    int l = L[q], r = R[q];
    vector<long long> ans(r-l+1);
    stack<int> st;

    // Find answer contributions from left
    st.push(l-1);
    long long sum = 0;
    for (int i = l; i <= r; ++i) {
      while (st.top() >= l && H[st.top()] <= H[i]) {
        int x = st.top();
        st.pop();
        sum += (long long)(x-st.top())*(H[i]-H[x]);
      }
      st.push(i);
      sum += H[i];
      ans[i-l] += sum;
    }
    while (!st.empty()) st.pop();

    // Find answer contributions from right
    st.push(r+1);
    sum = 0;
    for (int i = r; i >= l; --i) {
      while (st.top() <= r && H[st.top()] <= H[i]) {
        int x = st.top();
        st.pop();
        sum += (long long)(st.top()-x)*(H[i]-H[x]);
      }
      st.push(i);
      sum += H[i];
      ans[i-l] += sum;
    }
    while (!st.empty()) st.pop();

    // Choose best answer
    long long minCost = 1e18;
    for (int i = l; i <= r; ++i) {
      ans[i-l] -= H[i]; // counted from both sides
      minCost = min(minCost, ans[i-l]);
    }
    C[q] = minCost;
  }
  return C;
}

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