Submission #970519

#	Time	Username	Problem	Language	Result	Execution time	Memory
970519		jamesbamber	Meetings (IOI18_meetings)	C++17	19 / 100	5563 ms	7832 KiB

meetings

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

typedef long long ll;

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int Q = L.size();
    vector<ll> ans(Q);
    

    for(int q=0; q<Q; q++){
        int l = L[q], r = R[q]+1;
        int sz = r-l;
        vector<ll> pref(sz), suff(sz);
        stack<pair<ll,ll>> s;
        ll curr = 0;
        for(int i=l; i<r; i++){
            ll rm = 0;
            while(s.size() and s.top().first <= H[i]){
                rm += s.top().second;
                curr -= s.top().first*s.top().second;
                s.pop();
            }
            s.push({H[i], rm+1});
            curr += H[i]*(rm+1);
            pref[i-l] = curr;
        }

        while(s.size()) s.pop();
        curr = 0;
        for(int i=r-1; i>=l; i--){
            ll rm = 0;
            while(s.size() and s.top().first <= H[i]){
                rm += s.top().second;
                curr -= s.top().first*s.top().second;
                s.pop();
            }
            s.push({H[i], rm+1});
            curr += H[i]*(rm+1);
            suff[i-l] = curr;
        }

        ll mn = min(pref[sz-1], suff[0]);
        for(int i=1; i<sz; i++){
            mn = min(mn, pref[i-1]+suff[i]);
        }
        ans[q] = mn;
    }

    return ans;
}

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