Submission #1244852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244852		joenpoenmanalt	Meetings (IOI18_meetings)	C++20	19 / 100	5589 ms	5852 KiB

meetings

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef pair<int, int> ii;

#define ALL(x) begin(x), end(x)


std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
    int n = H.size();
    int Q = L.size();
    std::vector<long long> C(Q);
    
    for (int i = 0; i < Q; i++) {
        int l = L[i], r = R[i];
        stack<ii> stk;
        vll suf(r+2, 0);
        for (int j = r; j >= l; j--) {
            while (stk.size() && H[j] >= stk.top().first) stk.pop();
            ll res = 0;
            if (stk.empty()) {
                res = 1LL*(r-j+1)*H[j];
                stk.push({H[j], j});
            } else {
                res = suf[stk.top().second] + 1LL*(stk.top().second-j)*H[j];
                stk.push({H[j], j});
            }
            suf[j] = res;
        }

        while (stk.size()) stk.pop(); // clear

        vll pre(r+1);
        for (int j = l; j <= r; j++) {
            while (stk.size() && H[j] >= stk.top().first) stk.pop();
            ll res = 0;
            if (stk.empty()) {
                res = 1LL*(j-l+1)*H[j];
                stk.push({H[j], j});
            } else {
                res = pre[stk.top().second] + 1LL*(j-stk.top().second)*H[j];
                stk.push({H[j], j});
            }
            pre[j] = res;
        }

        ll best = 1e18;
        for (int j = l; j <= r; j++) {
            best = min(best, pre[j] + suf[j+1]);
        }
        C[i] = best;
    }

    return C;
}


/*
4 2
2 4 3 5
0 2
1 3
*/

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