제출 #282057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282057		Haunted_Cpp	모임들 (IOI18_meetings)	C++17	19 / 100	774 ms	619156 KiB

meetings

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


typedef long long i64;

const int MAX_N = 5e3 + 5;

i64 r[MAX_N][MAX_N];
i64 l[MAX_N][MAX_N];

vector<i64> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  const int n = H.size();
  const int q = L.size();
  vector<i64> C(q);
  for (int i = 0; i < n; i++) {
    int mx;
    mx = H[i];
    for (int j = i + 1; j < n; j++) {
      mx = max(mx, H[j]);
      r[i][j] = r[i][j - 1] + mx;
    }
    mx = H[i];
    l[i][i] = mx;
    for (int j = i - 1; ~j; j--) {
      mx = max(mx, H[j]);
      l[i][j] = l[i][j + 1] + mx;
    }
  }
  for (int i = 0; i < q; i++) {
    const int lo = L[i];
    const int hi = R[i];
    i64 mn = 1e18;
    for (int j = lo; j <= hi; j++) {
      i64 left_side = l[j][lo];
      i64 right_side = r[j][hi];
      mn = min(mn, left_side + right_side);
    }
    C[i] = mn;
  }
  return C;
}

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