Submission #278861

#	Time	Username	Problem	Language	Result	Execution time	Memory
278861		ggooroo	모임들 (IOI18_meetings)	C++14	19 / 100	1016 ms	786432 KiB

meetings

#include "meetings.h"
#include<cstdio>
#include<iostream>
#include<vector>
#define N 5005
typedef long long ll;

using namespace std;
ll n, Q, mx[N][N], s[N][N], h[N], l[N], r[N];
vector<ll> ans;
ll f(ll p, ll q) {
	if (q < 0) return 0;
	return s[p][q];
}

std::vector<long long> minimum_costs(std::vector<int> hh, std::vector<int> lll,
                                     std::vector<int> rr) {
	ll i, j, x, mn;
	n = hh.size();
	Q = lll.size();
	for (i = 0; i < n; i++) {
		h[i] = hh[i];
	}
	for (i = 0; i < Q; i++) {
		l[i] = lll[i];
		r[i] = rr[i];
	}
	for (i = 0; i < n; i++) {
		mx[i][i] = h[i];
		for (j = i - 1; j >= 0; j--) {
			mx[i][j] = max(mx[i][j + 1], h[j]);
		}
		for (j = i +1; j < n; j++) {
			mx[i][j] = max(mx[i][j - 1], h[j]);
		}
		s[i][0] = mx[i][0];
		for (j = 1; j < n; j++) s[i][j] = s[i][j - 1] + mx[i][j];
	}
	for (i = 0; i < Q; i++) {
		mn = -1;
		for (j = 0; j < n; j++) {
			x = f(j, r[i]) - f(j, l[i] - 1);
			if (mn == -1 || x < mn) mn = x;
		}
		ans.push_back(mn);
	}
	return ans;
}

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