Submission #1199175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199175		theyeia	Meetings (IOI18_meetings)	C++20	19 / 100	805 ms	851968 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pi = pair<int,int>;
const int MOD = 1e9 + 7;
#define F first
#define S second
#define sz(x) int((x).size())
#define sor(x) sort(begin(x), end(x))
#define FOR(i, a, b) for (int i = a; i < b; i++)

vi H, L, R;

vector<vl> Maxes, Prefix, Suffix;

vl prefix(vl A) {
    int k = sz(A);
    ll mx = 0, s = 0;

    vl Maxes, Pref;

    FOR(i, 0, k) {
        mx = max(A[i], mx);
        Maxes.push_back(mx);
    }

    FOR(i, 0, k) {
        s += Maxes[i];
        Pref.push_back(s);
    }

    return Pref;
}

vl minimum_costs(vi H0, vi L0, vi R0) {
    int n = H0.size(), q = L0.size();

    for (auto h : H0) H.push_back(h);
    for (auto l : L0) L.push_back(l);
    for (auto r : R0) R.push_back(r);

    vl Ans(q);
    Maxes.resize(n, vl(n, 0));
    Prefix.resize(n, vl(n, MOD));
    Suffix.resize(n, vl(n, MOD));

    FOR(l, 0, n) {
        int mx = 0;
        FOR(r, l, n) {
            mx = max(mx, H[r]);
            Maxes[l][r] = (ll)mx;
        }
    }

    FOR(l, 0, n) {
        Prefix[l][l] = Maxes[l][l];

        FOR(r, l + 1, n) {
            Prefix[l][r] = Prefix[l][r - 1] + Maxes[l][r];
        }
    }

    FOR(r, 0, n) {
        Suffix[r][r] = Maxes[r][r];

        for (int l = r - 1; l >= 0; l--) {
            Suffix[l][r] = Suffix[l + 1][r] + Maxes[l][r];
        }
    }

    FOR(i, 0, q) {
        int l = L[i], r = R[i];

        ll Best = 1e18;

        FOR(j, l, r + 1){
            Best = min(Best, Suffix[l][j] + Prefix[j][r] - H[j]);
        }

        Ans[i] = Best;
    }

    //for (auto val : Ans) cout << val << " "; cout << "oink1 " << endl;

    return Ans;
}

//#include "grader.cpp"

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