제출 #139303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
139303		Meloric	모임들 (IOI18_meetings)	C++14	19 / 100	5586 ms	5080 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define X first
#define Y second

using namespace std;

ll ez(int l, int r, vector<int>& H){
    vector<ll> le, ri, st, am;
    le.assign(H.size(), 0);
    ri.assign(H.size(), 0);
    ll cur = 0;
    for(int i = l; i<=r; i++){
        ll tmp = 1;
        while(st.size()>0 && st.back() <= H[i]){
            tmp+=am.back();
            cur-=am.back()*st.back();
            st.pop_back();
            am.pop_back();
        }
        cur+=tmp*H[i];
        le[i] = cur;
        st.pb((ll)H[i]);
        am.pb(tmp);
    }
    cur = 0;
    st.clear(); am.clear();
    for(int i = r; i>=l; i--){
        ll tmp = 1;
        while(st.size()>0 && st.back() <= H[i]){
            tmp+=am.back();
            cur-=am.back()*st.back();
            st.pop_back();
            am.pop_back();
        }
        cur+=tmp*H[i];
        ri[i] = cur;
        st.pb((ll)H[i]);
        am.pb(tmp);
    }
    ll ret = 1e15;
    for(int i = l; i<=r; i++){
        ret = min(ret, le[i]+ri[i]-H[i]);
    }
    return ret;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,
                                     vector<int> R) {
  int Q = L.size();
  vector<ll> C(Q);
  for (int j = 0; j < Q; ++j) {
    C[j] = ez(L[j], R[j], H);
  }
  return C;
}

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