Submission #1220966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220966		cpdreamer	Meetings (IOI18_meetings)	C++20	19 / 100	5592 ms	7476 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = (ll)1e9+7;
#define P pair
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    ll q=(ll)L.size();
    ll n=(ll)H.size();
    V<ll>C;
    V<ll>h(n+1);
    for (ll i=1;i<=n;i++) {
        h[i]=H[i-1];
    }
    V<ll>idl(n+1,0),idr(n+1,n+1);
    for (ll i=1;i<=n;i++) {
        for (ll j=i-1;j>=1;j--) {
            if (h[j]>=h[i]) {
                idl[i]=j;
                break;
            }
        }
        for (ll j=i+1;j<=n;j++) {
            if (h[j]>=h[i]) {
                idr[i]=j;
                break;
            }
        }
    }
    for (ll i=0;i<q;i++) {
        ll l=L[i]+1,r=R[i]+1;
        V<ll>dpl(n+2,0),dpr(n+2);
        for (ll j=l;j<=r;j++) {
            ll id=max(idl[j],l-1);
            dpl[j]+=dpl[id]+(j-id)*h[j];
        }
        for (ll j=r;j>=l;j--) {
            ll id=min(idr[j],r+1);
            dpr[j]+=dpr[id]+(id-j)*h[j];
        }
        ll ans=LLONG_MAX;
        for (ll j=l;j<=r;j++) {
            ans=min(ans,dpl[j]+dpr[j]-h[j]);
        }
        C.pb(ans);
    }
    return C;

}

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