Submission #115527

#	Time	Username	Problem	Language	Result	Execution time	Memory
115527		onjo0127	Meetings (IOI18_meetings)	C++11	19 / 100	748 ms	598992 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

int MH[5009][5009];
long long PS[5009][5009];

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int Q = L.size(), N = H.size();
    vector<long long> C(Q);
    for(int i=0; i<N; i++) {
        for(int j=i, mx=H[i]; j>=0; j--) mx = max(mx, H[j]), MH[i][j] = mx;
        for(int j=i, mx=H[i]; j<N; j++) mx = max(mx, H[j]), MH[i][j] = mx;
        PS[i][0] = MH[i][0];
        for(int j=1; j<N; j++) PS[i][j] = PS[i][j-1] + MH[i][j];
    }
    for(int i=0; i<Q; i++) {
        long long ans = 1LL * 1e18;
        for(int j=L[i]; j<=R[i]; j++) {
            long long x = PS[j][R[i]] - (L[i] ? PS[j][L[i]-1] : 0);
            ans = min(ans, x);
        }
        C[i] = ans;
    }
    return C;
}

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