Submission #1216350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216350		not_amir	Meetings (IOI18_meetings)	C++20	19 / 100	507 ms	851968 KiB

meetings

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

typedef pair<int, int> pii;

typedef long long ll;

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int N = H.size();
    vector mx(N, vector<pii>(N));
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            if (i == j)
                mx[i][j] = {H[i], i};
            else
                mx[i][j] = max(mx[i][j - 1], {H[j], j});
        }
    }
    vector dp(N, vector<ll>(N));
    for (int l = 0; l < N; l++) {
        for (int i = 0; i + l < N; i++) {
            int j = i + l;
            auto [m, k] = mx[i][j];
            dp[i][j] = 1ll * m * (l + 1);
            if (i < k)
                dp[i][j] = min(dp[i][j], dp[i][k - 1] + 1ll * m * (j - k + 1));
            if (k < j)
                dp[i][j] = min(dp[i][j], dp[k + 1][j] + 1ll * m * (k - i + 1));
        }
    }
    int Q = L.size();
    vector<ll> res(Q);
    for (int i = 0; i < Q; i++)
        res[i] = dp[L[i]][R[i]];
    return res;
}
/*
4 2
2 4 3 5
0 2
1 3
 */

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