Submission #81927

#	Time	Username	Problem	Language	Result	Execution time	Memory
81927		wleung_bvg	Meetings (IOI18_meetings)	C++14	0 / 100	491 ms	398884 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
using ll=long long;constexpr const char nl='\n',sp=' ';

const int MAXN = 5005;

ll cost[MAXN][MAXN], dp[MAXN][MAXN];
int ind[MAXN][MAXN];

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    for (int j = 0; j < sz(H); j++) cost[0][j] = 0;
    for (int i = 0; i < sz(H); i++) {
        for (int j = i, mx = H[i]; j < sz(H); j++) cost[i + 1][j] = mx = max(mx, H[j]);
        for (int j = i, mx = H[i]; j >= 0; j--) cost[i + 1][j] = mx = max(mx, H[j]);
    }
    for (int i = 0; i < sz(H); i++) for (int j = 0; j < sz(H); j++) cost[i + 1][j] += cost[i][j];
    for (int l = 0; l < sz(H); l++) {
        ll mx = H[l]; int mxInd = l;
        for (int r = l; r < sz(H); r++) {
            if (mx < H[r]) { mx = H[r]; mxInd = r; }
            ind[l][r] = mxInd;
            dp[l][r] = 0x3f3f3f3f3f3f3f3f;
        }
    }
    for (int l = 0; l < sz(H); l++) for (int m = l, r = l; r < sz(H); r++) while (true) {
        dp[l][r] = min(dp[l][r], cost[r + 1][m] - cost[l][m]);
        if (m + 1 < ind[l][r]) m++;
        else break;
    }
    for (int r = sz(H) - 1; r >= 0; r--) {
        ll mx = H[r]; int mxInd = r;
        for (int l = r; l >= 0; l--) {
            if (mx < H[l]) { mx = H[l]; mxInd = l; }
            ind[r][l] = mxInd;
        }
    }
    for (int r = sz(H) - 1; r >= 0; r--) for (int m = r, l = r; l >= 0; l--) while (true) {
        dp[l][r] = min(dp[l][r], cost[r + 1][m] - cost[l][m]);
        if (m - 1 > ind[l][r]) m--;
        else break;
    }
    vector<ll> ret(sz(L));
    for (int i = 0; i < sz(L); i++) ret[i] = dp[L[i]][R[i]];
    return ret;
}

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