Submission #416573

#	Time	Username	Problem	Language	Result	Execution time	Memory
416573		wiwiho	Meetings (IOI18_meetings)	C++14	19 / 100	5570 ms	7412 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>

#define eb emplace_back
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define pob pop_back()
#define iter(a) a.begin(), a.end()

using namespace std;

typedef long long ll;

using pll = pair<ll, ll>;

vector<int> h;

ll solve(int l, int r){
    //cerr << "query " << l << " " << r << "\n";
    vector<pll> dq;
    ll sum = 0;
    vector<ll> ans(r - l + 1);
    for(int i = l; i <= r; i++){
        ll len = 1;
        while(!dq.empty() && dq.back().F <= h[i]){
            sum -= dq.back().F * dq.back().S;
            len += dq.back().S;
            dq.pob;
        }
        sum += h[i] * len;
        dq.eb(mp(h[i], len));
        //cerr << i << " " << sum << "\n";
        ans[i - l] += sum;
    }
    dq.clear();
    sum = 0;
    for(int i = r; i >= l; i--){
        ll len = 1;
        while(!dq.empty() && dq.back().F <= h[i]){
            sum -= dq.back().F * dq.back().S;
            len += dq.back().S;
            dq.pob;
        }
        sum += h[i] * len;
        //cerr << i << " " << sum << "\n";
        dq.eb(mp(h[i], len));
        ans[i - l] += sum - h[i];
    }
    return *min_element(iter(ans));
}

vector<ll> minimum_costs(vector<int> H, vector<int> L,
                                     vector<int> R) {
    h = H;
    int m = L.size();
    vector<ll> c(m);
    for(int i = 0; i < m; i++) c[i] = solve(L[i], R[i]);
    
    return c;
}

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