제출 #246785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246785		srvlt	Meetings (IOI18_meetings)	C++14	19 / 100	846 ms	301688 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n = 5003;
int mx[n][n];
ll p[n][n], s[n][n];

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int Q = L.size();
  std::vector<long long> C(Q);
  int N = SZ(H);
  
	for (int i = 0; i < N; i++)
		for (int j = i; j < N; j++)
			mx[i][j] = (i == j) ? H[i] : max(mx[i][j - 1], H[j]);
	for (int j = 0; j < N; j++)
		for (int i = j; i >= 0; i--)
			p[i][j] = (i == j) ? H[i] : (p[i + 1][j] + mx[i][j]);
	for (int i = 0; i < N; i++)
		for (int j = i; j < N; j++)
			s[i][j] = (i == j) ? H[i] : (s[i][j - 1] + mx[i][j]);
	for (int i = 0; i < Q; i++) {
		int l = L[i], r = R[i];
		ll res = 1e18;
		for (int i = l; i <= r; i++)
			res = min(res, p[l][i] + s[i][r] - H[i]);
		C[i] = res;
	}
	
  return C;
}

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