Submission #1244925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244925		jeroenodb	Meetings (IOI18_meetings)	C++20	19 / 100	5590 ms	5364 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) begin(x),end(x)
const int oo = 1e9;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int Q = L.size();
    int  n =H.size();
    std::vector<long long> C;
    vi l(n);
    for(int i=0;i<n;++i) {
        l[i]=i-1;
        while(l[i]>=0 and H[l[i]]<=H[i]) {
            l[i]=l[l[i]];
        }
    }
    vi r(n);
    for(int i=n-1;i>=0;--i) {
        r[i]=i+1;
        while(r[i]<n and H[r[i]]<=H[i]) {
            r[i] = r[r[i]];
        }
    }

    for(int i=0;i<Q;++i) {
        int ql = L[i],qr = R[i];
        vector<ll> dpl(n),dpr(n);
        for(int i=ql;i<=qr;++i) {
            if(l[i]<ql) {
                dpl[i] = (i-ql+1)*ll(H[i]);

            } else dpl[i] = (i-l[i])*ll(H[i]) + dpl[l[i]];
        }
        for(int i=qr;i>=ql;--i) {
            if(r[i]>qr) {
                dpr[i] = (qr-i+1)*ll(H[i]);

            } else dpr[i] = (r[i]-i)*ll(H[i]) + dpr[r[i]];
        }
        ll ans = 1e18;
        for(int i=ql;i<=qr;++i) {
            ans=min(ans,dpl[i]+dpr[i]-H[i]);
        }
        C.push_back(ans);
        
    }
    return C;
}

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