Submission #836231

#	Time	Username	Problem	Language	Result	Execution time	Memory
836231		Johann	Meetings (IOI18_meetings)	C++14	0 / 100	5558 ms	6948 KiB

meetings

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

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 1LL << 60;

vi minimum_costs(std::vector<int> H, std::vector<int> L,
                 std::vector<int> R)
{
  int N = sz(H);
  int Q = L.size();
  vi ans(Q);
  vi dpL(N), dpR(N);
  for (int j = 0; j < Q; ++j)
  {
    ll tmp = 0;
    stack<pii> st; // { value, number}
    st.push({INF, 0});
    for (int i = L[j]; i <= R[j]; ++i)
    {
      int num = 1;
      while (st.top().first <= H[i])
      {
        tmp -= st.top().first * st.top().second;
        num += st.top().second;
        st.pop();
      }
      st.push({H[i], num});
      tmp += H[i] * num;
      dpL[i] = tmp;
    }

    tmp = 0;
    while (!st.empty())
      st.pop();
    st.push({INF, 0});
    for (int i = R[j]; i >= L[j]; --i)
    {
      int num = 1;
      while (st.top().first <= H[i])
      {
        tmp -= st.top().first * st.top().second;
        num += st.top().second;
        st.pop();
      }
      st.push({H[i], num});
      tmp += H[i] * num;
      dpR[i] = tmp;
    }

    ans[j] = INF;
    for (int i = L[j]; i <= R[j]; ++i)
    {
      ans[j] = min(ans[j], dpL[i] + dpR[i] - H[i]);
    }
  }
  return ans;
}

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