Submission #1044788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044788		RecursiveCo	Meetings (IOI18_meetings)	C++17	19 / 100	5581 ms	7396 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

#define out(o) cout << o

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int N = H.size();
    int Q = L.size(); // = R.size()
    // assumed to be subtasks 1 and 2
    vector<long long> ans;
    for (int i = 0; i < Q; i++) {
        int l = L[i];
        int r = R[i];
        vector<long long> left;
        stack<pair<int, int>> st;
        st.push({H[l], 1});
        left.push_back((long long) H[l]);
        long long cur = H[l];
        for (int j = l + 1; j <= r; j++) {
            int change = 1;
            while (!st.empty() && st.top().first <= H[j]) {
                change += st.top().second;
                cur -= ((long long) (st.top().first)) * ((long long) (st.top().second));
                st.pop();
            }
            st.push({H[j], change});
            cur += ((long long) (H[j])) * ((long long) (change));
            left.push_back(cur);
        }
        while (!st.empty()) st.pop();
        st.push({H[r], 1});
        vector<long long> right;
        right.push_back((long long) H[r]);
        cur = H[r];
        for (int j = r - 1; j >= l; j--) {
            int change = 1;
            while (!st.empty() && st.top().first <= H[j]) {
                change += st.top().second;
                cur -= ((long long) (st.top().first)) * ((long long) (st.top().second));
                st.pop();
            }
            st.push({H[j], change});
            cur += ((long long) (H[j])) * ((long long) (change));
            right.push_back(cur);
        }
        reverse(right.begin(), right.end());
        long long here = 1e18;
        for (int j = 0; j < r - l + 1; j++) here = min(here, left[j] + right[j] - ((long long) H[l + j]));
        ans.push_back(here);
    }
    return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:9:9: warning: unused variable 'N' [-Wunused-variable]
    9 |     int N = H.size();
      |         ^

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