Submission #599972

#	Time	Username	Problem	Language	Result	Execution time	Memory
599972		MohamedFaresNebili	Meetings (IOI18_meetings)	C++14	19 / 100	502 ms	402560 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

                using namespace std;

                using ll = long long;
                using ld = long double;
                using ii = pair<ll, ll>;
                using vi = vector<int>;

                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound

                const int MOD = 1e9 + 7;

                ll N, Q, DP[5005][5005], SP[100001][20], LOG[100001];
                ll query(int i, int j) {
                    int K = LOG[j - i + 1];
                    return max(SP[i][K], SP[j - (1 << K) + 1][K]);
                }

                vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
                    LOG[1] = 0; N = H.size(), Q = L.size();
                    for(int l = 2; l <= N; l++)
                        LOG[l] = LOG[l / 2] + 1;
                    for(int l = 0; l < N; l++)
                        SP[l][0] = H[l];
                    for(int l = 1; l < 20; l++)
                        for(int i = 0; i + (1 << l) <= N; i++)
                            SP[i][l] = max(SP[i][l - 1], SP[i + (1 << (l - 1))][l - 1]);
                    for(int l = 0; l < N; l++) {
                        DP[l][l] = H[l];
                        for(int i = l + 1; i < N; i++) {
                            DP[l][i] = DP[l][i - 1];
                            DP[l][i] += query(l, i);
                        }
                        for(int i = l - 1; i >= 0; i--) {
                            DP[l][i] = DP[l][i + 1];
                            DP[l][i] += query(i, l);
                        }
                    }
                    vector<ll> res(Q, -1);
                    for(int l = 0; l < Q; l++) {
                        ll best = 1000000000LL * 1LL * 1000000000LL;
                        for(int i = L[l]; i <= R[l]; i++) {
                            ll A = DP[i][R[l]];
                            if(i != L[l]) A += DP[i][L[l]] - H[i];
                            best = min(best, A);
                        }
                        res[l] = best;
                    }
                    return res;
                }

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