Submission #139256

#	Time	Username	Problem	Language	Result	Execution time	Memory
139256		fredbr	Meetings (IOI18_meetings)	C++17	19 / 100	5526 ms	5800 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll const inf = 0x3f3f3f3f3f3f3f3f;

vector<ll> minimum_costs(vector<int> h, vector<int> L,
                                        vector<int> R) {
    int n = h.size();
    vector<int> a(n), b(n);

    stack<int> pre;

    for (int i = 0; i < n; i++) {
        while (!pre.empty() and h[pre.top()] < h[i]) {
            b[pre.top()] = i;
            pre.pop();
        }
        pre.push(i);
    }
    while (!pre.empty()) {
        b[pre.top()] = n;
        pre.pop();
    }

    reverse(h.begin(), h.end());

    for (int i = 0; i < n; i++) {
        while (!pre.empty() and h[pre.top()] < h[i]) {
            a[pre.top()] = i;
            pre.pop();
        }
        pre.push(i);
    }
    while (!pre.empty()) {
        a[pre.top()] = n;
        pre.pop();
    }

    reverse(h.begin(), h.end());

    for (int& i : a) i = n-1-i;
    reverse(a.begin(), a.end());

    int q = L.size();
    
    // for (int i : a) cout << i << " ";
    // cout << "\n";
    // for (int i : b) cout << i << " ";
    // cout << "\n";

    vector<ll> res;
    for (int at = 0; at < q; at++) {
        ll ans = inf;

        int l = L[at], r = R[at];

        vector<ll> resl(r-l+1);
        vector<ll> resr(r-l+1);

        for (int i = l; i <= r; i++) {
            if (a[i] < l) resl[i-l] = ll(h[i])*(i-l+1);
            else resl[i-l] = resl[a[i]-l] + ll(i-a[i])*h[i];
        }

        for (int i = r; i >= l; i--) {
            if (b[i] > r) resr[i-l] = ll(h[i])*(r-i+1);
            else resr[i-l] = resr[b[i]-l] + ll(b[i]-i)*h[i];
        }

        for (int i = l; i <= r; i++) {
            ans = min(ans, resl[i-l] + resr[i-l] - h[i]);
        }

        res.push_back(ans);
    }

    return res;
}

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