Submission #1220964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220964		cpdreamer	Meetings (IOI18_meetings)	C++20	0 / 100	5592 ms	6296 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) {
    int q=(int)L.size();
    int n=(int)H.size();
    V<ll>C;
    V<int>h(n+1);
    for (int i=1;i<=n;i++) {
        h[i]=H[i-1];
    }
    V<int>idl(n+100,0),idr(n+100,n+100);
    for (int i=1;i<=n;i++) {
        for (int j=i-1;j>=1;j--) {
            if (h[j]>=h[i]) {
                idl[i]=j;
                break;
            }
        }
        for (int j=i+1;j<=n;j++) {
            if (h[j]>=h[i]) {
                idr[i]=j;
                break;
            }
        }
    }
    for (int i=0;i<q;i++) {
        int l=L[i]+1,r=R[i]+1;
        V<ll>dpl(n+200,0),dpr(n+200);
        for (int j=l;j<=r;j++) {
            int id=max(idl[j],l-1);
            dpl[j]+=dpl[id]+(j-id)*h[j];
        }
        for (int j=r;j>=l;j--) {
            int id=min(idr[j],r+1);
            dpr[j]+=dpr[id]+(id-j)*h[j];
        }
        ll ans=LLONG_MAX;
        for (int j=l;j<=r;j++) {
            ans=min(ans,dpl[j]+dpr[j]-h[j]);
        }
        C.pb(ans);
    }
    return C;

}

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