제출 #599957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
599957		MohamedFaresNebili	Meetings (IOI18_meetings)	C++14	0 / 100	329 ms	385032 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];
                int 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[l][i] = 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);
                        }
                    }
                    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[L[l]][i - 1];
                            best = min(best, A);
                        }
                        res[l] = best;
                    }
                    return res;
                }

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