Submission #954408

#	Time	Username	Problem	Language	Result	Execution time	Memory
954408		Macker	Meetings (IOI18_meetings)	C++17	19 / 100	5550 ms	8328 KiB

meetings

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

using namespace std;

typedef long long ll;
typedef long double ld;
#define int ll
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)

int get_mn(vector<int> v){
    int n = v.size();
    vector<int> res(n, 0);
    FOR(w, 2){
        stack<pair<int, int>> s;
        s.push({INT_MAX, -1});
        int cur = 0;
        FOR(i, n){
            while(s.top().ff <= v[i]){
                auto [h, j] = s.top(); s.pop();
                cur -= h * (j - s.top().ss);
            }
            cur += v[i] * (i - s.top().ss);
            res[w ? n - i - 1 : i] += cur;
            s.push({v[i], i});
        }
        reverse(all(v));
    }
    FOR(i, n) res[i] -= v[i];
    return *min_element(all(res));
}

vector<int> minimum_costs(vector<signed> H, vector<signed> L, vector<signed> R) {
    int q = L.size();
    int n = H.size();
    vector<int> res(q);
    for (int j = 0; j < q; ++j) {
        vector<int> v;
        for (int i = L[j]; i <= R[j]; i++) {
            v.push_back(H[i]);
        }
        res[j] = get_mn(v);
    }
    return res;
}

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:39:9: warning: unused variable 'n' [-Wunused-variable]
   39 |     int n = H.size();
      |         ^

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